edu(b)log

Formal Proofs on Grammars

Any time that you want a general approach to proving properties of grammars and languages, keep these things in mind…

• Try induction first. Sometimes a direct proof or proof by contradiction is the way to go, but induction is the most likely tool to use for grammars.
• Given some grammar, G = (N, Σ, P, S), if you're asked to prove x ∈ L(G), then you just need to come up with a specific sequence of rules (find a string π ∈ P⁺ (sequence of one or more values in P) such that S ⇒ x. So the existence of π is the proof that x ∈ P. It demonstrates that there is some computation path that will produce x.

There may be more than one left-most or right-most derivation. One language might have more than one left-most derivation under one grammar and the same language might have only one left-monst derivation under a different grammar (that's called unambiguous grammar). This is the type of grammar we want for compilers. We want different parsers to parse the same code the same way.

S ⇒ x
S ⇒ 0

You can construct an inductive proof based on either |π| (number of steps to derivation or |x| (length of sentenial form). Usually it's easier to do induction on the length of the derivation.

1: S → aSb
2: S → λ

Conjecture:
L(G) = { aⁿbⁿ | n ≥ 0 }

To prove this, you have to show two things:

1. If x ∈ L(G) implies x ∈ { aⁿbⁿ | n ≥ 0 }
2. If y ∈ { aⁿbⁿ | n ≥ 0 } then y ∈ L(G)

There is a difference. The first says the terminal string has to be of the form { aⁿbⁿ | n ≥ 0 }. You have to prove by induction that if S ⇒ x ∈ Σ*, then x=aⁿbⁿ for some n ≥ 0.

Also, you must prove that if x = aⁿbⁿ, n ≥ 0, then there exists some π_x such that S ⇒ x ∈ Σ^x.

Hypothesis: For n ≥ 0, S ⇒ aⁿbⁿ.

Prove by induction on n:

1. Basis Case (n=0): S ⇒(2) λ = a⁰b⁰ = λb⁰ = λλ = λ
2. Induction Case: Assume Induction Hypothesis holds for all k, 0 ≤ k ≤ n. Show that it holds for n+1.
   
   Show that: S ⇒ aⁿ⁺¹bⁿ⁺¹

S (1)⇒ aSb (1ⁿ2)⇒ aaⁿbⁿb = aⁿ⁺¹bⁿ⁺¹ (using the inductive hypothesis).

Inductive Definitions, cont.

We're looking for different ways to specify formal specification systems. Three formal systems for specifying languages or sets:

1. Set notation
2. Grammars
3. Inductive definitions

Recall that inductive definitions have three parts:

1. Basis Rule that declares a finite subset of S.
2. A set of inductive rules: R₁, R₂, … R_n where each rule takes the form: if P(x) then f(x) ⊆ S. P(x) is some predicate true about an existing member x of S. f(x) is a finite set of potentially new members of S. Even though f(x) may be finite, some of those members may already exist in S. So it doesn't guarantee that all or any members will be new.
3. Standard Closure Rule: Nothing belongs to S that cannot be gotten from rules (1) and (2). You have to be able to define membership exclusively in terms of some finite application of these rules.

S_n is the set of all members of S you can get by n applications of the inductive rules.

S₀ is the set gotten by no applications of the inductive rules — in other words, it is the set obtained by the basis rule.

Example 6

illustrates how we can use inductive definitions to prove something about languages. It also illustrates that any time we specify a language in some formal system we are burdened with proving that it does define the language that we say it does.

L = { (ab)ⁿ | n ≥ 0 } = { λ, ab, abab, ababab, … }

Inductive definition of the same language (L' — give it a different name until you've proved that L'=L):

Basis: λ ∈ L'

Inductive Rules:
R₁: If x ∈ L' then xab ∈ L' Choose any string known to exist in L' and you can get a new string in L' by concatenating ab on the end of it… by predicate)

Theorem: L = L'. In order to prove two sets are equal, you must show that each is a subset of the other.

So prove: L ∈ L' and L' ∈ L.

Lemma 1

Claim: L'_n (any member of L' that's earned membership by n applications of the inductive rules) … L'_n = { (ab)^k | 0 ≤ k ≤ n }

(a) x ∈ L'_n ⇒ x ∈ { (ab)^k | 0 ≤ k ≤ n }

(b) If x ∈ (ab)ⁿ for some n ≥ 0, then x ∈ L'ⁿ.

Prove (a) and (b) by induction on n. You'll really prove both directions at once.

Basis. L'₀ = { (ab)^k | 0 ≤ k ≤ 0 }
LHS: L'₀ = { λ }
RHS: { (ab)⁰ } = { λ }

So we have established that LHS = RHS for n=0.

Inductive Case.
Inductive Hypothesis: IH(n) : L'_n = { (ab)^k | 0 ≤ k ≤ n } for some m ≥ 0.
Show: IH(n) ⇒ IH(n+1)

LHS: Consider L'_n+1
= L'_n ∪ { y | y ∈ L' by some application R₁(x) x ∈ L'}
By IH(n) = { (ab)^k | 0 ≤ k ≤ n } ∪ { (ab)^kab | 0 ≤ k ≤ n }
≡ ∪ { (ab)^k+1 | 0 ≤ k ≤ n }
≡ ∪ { (ab)^k | 1 ≤ k ≤ n+1 }
= { (ab)^k | 0 ≤ k ≤ n } ∪ { (ab)^k | 1 ≤ k ≤ n } ∪ { (ab)ⁿ⁺¹ }
= { (ab)^k | 0 ≤ k ≤ n } ∪ { (ab)ⁿ⁺¹ }
= { (ab)^k | 0 ≤ k ≤ n+1 }
∴ that equality holds…

Now that our induction is complete we can assume that our lemma holds.

Case A. L ⊆ L'

Let x ∈ L. By definition of L, x = (ab)ⁿ for some n ≥ 0. By Lemma 1, L'_n (same n!) = { (ab)^k | 0 ≤ k ≤ n }
∴ x ∈ L'_n ⊆ L'
∴ L ⊆ L'

Case B.

Let x ∈ L'. Show that x ∈ L.

By definition of L' (closure rule), x ∈ L'_n for some n ≥ 0.
∴ x = (ab)ⁿ for some n ≥ 0
∴ By definition of L, x ∈ L.

You won't be expected to do proofs in this level of detail, but you will have to become familiar with the language used and the mental discipline…

Finite State Automata

We're going to start with Regular Languages and we'll characterize them in terms of Left-Linear Grammar, Right-Linear Grammar, and Finite State Machines (plus some others). We'll show that the family of regular languages is really an abstract data type closed under a number of operations. Then we'll move into context-free grammars with a very important test (the pumping lemma) that characterizes regular languages to test whether a language is regular or not. We'll develop some mathematical tools (algorithms) for detecting non-regular languages. We'll characterize those (CFGs) in terms of Type 2 grammars and Push-Down Automata. We'll study another extension of the pumping lemma, Pumping Lemma 2 that will get us outside of the context-free into the Turing Machine and Phrase Structured Grammars. These are the recursively innumerable languages, and the largest family of languages that we can describe with computers or computational devices.

Definition: A deterministic finite state machine (automaton) is a 5-tuple, M = (Q, Σ, δ q₀, A) where
Q = a non-empty, finite set of states.
Σ = alphabet of input symbols
q₀ ∈ Q is the initial state of M
A ⊆ Q is a set of accept states
δ = a function from Q x Σ → Q

What is the domain of δ? It's a cross-product: QxΣ = { (q,a) | q ∈ Q and a ∈ Σ }

|QxΣ| = |Q| * |Σ| if they're both finite.

The fact that it's a function means that it's defined on every member of the domain. So, for all (q,a) ∈ QxΣ, δ_n(q,a) ∈ Q. This means that if the machine is any of its states it will respond (it won't hang — it will go to some state / do something).

Exercise »

Design a valid finite state machine that accepts all valid Java identifiers.

Due: (no due date).

Chomsky cont. and Intro to Finite State Automata

Homework: Problem Set #1 »

The proof of the "sets" problem and a hint on another problem from last class are on the notes page and Problem Set #1 was posted on the Assignments Page. #4 is an important example because it defines all arithmetic expressions over addition, subtraction, multiplication, division, unary plus and unary minus. A context-free grammar that defines the syntax of most commonly used programming languages is usually no more complicated than this (in complexity). #5 will be the most difficult problem of the lot. Dr. Workman does not expect a formal proof, but he does expect you to get it started.

Due: (no due date).

Other administrative stuff… We will have the first quiz after we finish the Introduction to Finite State Automata. It won't be next week.

Review :: Phrase Structured Grammars

Chomsky Hierarchy of Grammar. You should have a firm understanding of the formal definitions of the different kinds of grammars. That will be on the quiz.

G = (N, Σ, P, S)
P = { u → v | u ∈ V*NV* and v ∈ V* }
Note: u ≠ v

Type-0 (Phrase Structured): No restrictions.

Type-1 (Context-Sensitive): Length of the right part is greater than or equal to the length of the left part ( |v| ≥ |u| ) ⇒ No erasing.

Type-2 (Context-Free): You can have only one non-terminal on the left side. u must be an element of N (u ∈ N). No left/right context. No restrictions on the right part.

Linear (special type of Context-Free): u ∈ N and v ∈ Σ*NΣ* ∪ Σ*

Type-3 (Right-Linear Grammars, also a subset of Context-Free): u ∈ N and v ∈ Σ*N ∪ Σ* If there is a non-terminal (there can be only one) it must be in the rightmost position (no symbols following the non-terminal).

Left-Linear (similar to Right-Linear, special type of Context-Free): u ∈ N and v ∈ N Σ* ∪ Σ*

Type 3 and Left-Linear are also called Regular Grammars.

LLG ≡ Left-Linear Grammar.
RLG ≡ Right-Linear Grammar.

Comment: u → v, where |v| < |u| is called an erasing rule. When u and v are both members of n it is called unit rules. u, v ∈ N (e.g. X → Y).

Example

G = ( N, Σ P, S )
N = { S, X, Y }
Σ = { a, b, c }
P = {
1: S → aS
2: S → Xbca
3: X → ccY
4: Y → λ
}

What type of grammar is this? Linear. When you mix both left- and right-linear rules you get a linear grammar.

New Stuff

Definition: Let Δ be a language specification (description) ______. The family of a language defined by Δ is

F_Δ = { L | L = L (δ) for some δ ∈ Δ }

For instance, Δ = Java; δ = a Java program. Δ = Set theory; δ = {x ∈ Σ* | |x|₀ = 25 }. Δ = English; δ = the set of all symbol strings of finite length taken from the alphabet, "0," and "1."

You can also have F₁ inside F₀. Language L may have an inifinite number of descriptions in Δ or in other formal systems. In the case of F₁ inside F₀, F₁ would be the smallest family containing L. Hmm…

If L ∈ F_Δ. TRUE or FALSE: If A ⊆ L then A ∈ F_Δ. False!! (In general).

The family of LLGs is the same as the family of RLGs. These are Language Families. As SETS, the grammars overlap (are not equal). In other words, there are examples of RLGs that are not LL and there are example of LLGs that are not RL and there are some that are both. The relationship of the families of grammars may be different from the languages.

What do the grammars look like that belong to both? How would you characterize grammars that are in the inner (overlapping) section?

u ∈ N AND v ∈ N ∪ Σ*

Rules will look like…

X → w, w ∈ Σ*
X → Y, Y ∈ N

What can you say about the family of those grammars?

F_both = Finite languages over Σ … e.g.:

S → λ
S → aa
S → b
S → cba

All of the languages outside F_both are infinite languages that can be described by either a LLG or a RLG.

If L ∈ F and A ⊆ L then it is not true, generally, that A ∈ F_Δ.

Consider Σ*.

A language, L, over Σ is any subset of Σ*.

|F_Σ| is uncountable

F_Σ = { L | L ⊆ Σ* } = ℘(Σ*)

The family of computable languages over Σ is just the Type-0 language over Σ.

∴ There are subsets of Σ* that are not computable!

Theorem: |N| = |Z| (N = Natural Numbers, Z = Rational Numbers = { a/b | b > 0 and a ∈ Integers }

Lemma A. If A ≤ S, then |A| ≤ |S|.

Proof: |A| ≤ |S| iff there exists a one-to-one function, f, from A to S.

Choose f to be the identity function; f(x) = x.

If x ∈ A, then f(x) ∈ A ⊆ S. ∴ f(x) ∈ S.

If x ≠ y, then f(x) ≠ f(y). ∴ f is one-to-one.

Lemma B. |N x N| = { (k, j) | k, j ∈ N }

f: N x N → N, where f is one-to-one and onto function.

f(0,0) = 0
f(1,0) = 1 (notice k + j = 1)
f(0,1) = 2 (notice k + j = 1)
f(2,0) = 3 (notice k + j = 2)
f(1,1) = 4 (notice k + j = 2)
f(0,2) = 5 (notice k + j = 2)
f(3,0) = 6 (notice k + j = 3)
f(3,1) = 7 (notice k + j = 3)
f(1,2) = 8 (notice k + j = 3)
f(0,3) = 9 (notice k + j = 3)
.
.
.

f(k,j) = g(k+j) + j = (Σ_i=0^k i) + j = (k+j)(k+j+1)/2 + j

Now we must show that this function is both one-to-one and onto.

To show f is one-to-one, we must show f(x) ≠ f(y) whenever x ≠ y.

Suppose (k,j) ≠ (k',j')
Case (a): k+j = k'+j'
f((k,j))-f((k',j')) = ((k+j)(k+j+1)/2 - (k'+j')(k'+j'+1)/2) + j - j' = j - j'

If j - j' = 0 then j = j'

k+j = k' + j so k = k' which leads to a contradiction of our assumption that (k,j) ≠ (k',j) ∴ j - j' > 0 ⇒ f((k,j)) ≠ f((k',j'))

Case (b): k' + j' > k + j
k' + j' = k + j + a, a > 0

f((k',j')) - f((k,j)) = (k+j+a)(k+j+a+1)/2 - (k+j)(k+j+1)/2 + j' - j
… j = aj + y, where y > 0 which cannot happen!

If we assume to the contrary that the two function values are equal then you get this relationship and that's possible so we conclude that (he trailed off who knows what he said)…

Let m ≥ 0 be a Natural Number. Find (k,j) such that f((k,j)) = m.

Define k to be the largest natural number such that k(k+1)/2 ≤ m.

j = m - k(k+1)/2

e.g. f((6,8)) = 29

Basically that's all we need to establish that f is one-to-one and onto. So what we've shown is that Lemma B is true.

Third step is to show that |Z| = |N|.

Z = { a/b | a ∈ J (integer) and b > 0 }

You can think of Z as a set of ordered pairs (a,b).

Z ⊆ J x N

By Lemma A, |Z| ≤ |J x N| = |N x N| = |N|. ∴ |Z| ≤ |N| and |N| ≤ |Z|

∴ |N| = |Z| (Can you prove this?)

We have done something in class to support the red part.

When you're dealing with inifinites is coming up with one-to-one, onto mappings. Unless you can give a formula, you don't have a proof!

Lemma B is a hint for problem #2.

Inductive Definitions

Inductive Definitions: Used to prove properties of the language that's defined by using induction. Inductive proofs work particularly well with inductive definitions.

Definition: An inductive definition of a set, S, consists of the following:

1. Basis Rule (R₀): Declaration or enumeration of some finite non-empty subset of S.
2. Finite set (possibly empty) of inductive rules (R_i>0): Rules of the form if P(x) then f(x) ⊆ S where x denotes some existing member of S, at the time that you apply the rule, and b(x) is some predicate true about x, and f(x) is a finite set of elements denoting potentially new member sets.
3. Completion Rule: a statement of the fact that nothing belongs to S that cannot be established by applying some finite sequence of the above rules.

Example

Define Σ*.

Basis Rule:

λ ∈ Σ*

Inductive Rules:

R₁: If x ∈ Σ* then ∀ a ∈ Σ, { ax, xa } ⊆ Σ* So… f(x) = { y | y = ax, y = xa, a ∈ Σ }

S_n = n applications of the Inductive Rule

Phrase Structured Grammars, etc.

Definition 2. Σ* = {x|x is a finite string over Σ}

What do we mean by "string"? Here we will use an inductive definition.

Basis: λ ∈ Σ* and |λ| = 0 and a ∈ Σ* for all a ∈ Σ and |a| = 1. Type conversion from symbols to string (char to string).

Inductive Step: If x ∈ Σ* then λ ⋅ x = x ⋅ λ = x
|a ⋅ x| = |x ⋅ a| = |x| + 1

"little dot": {(λ, λ)} ∪ Σ* ∗ Σ ∪ Σ ∗ Σ* → Σ*

Σ* set of strings

L ⊆ Σ* is a language over Σ

Concatenation: If L and M are strings over the same alphabet…

L, M ⊆ Σ*
L ⋅ M (Set concatenation.) = { x ⋅ y | x ∈ L and y ∈ M} (String concatenation.)

x ∈ L = { λ, ab, b }
y ∈ M = { ba, b, aa }

L ⋅ M = { (λ) ba, b, aa, (ab) abba, abb, abaa, (b) bba, bb, baa }

M ⋅ L ≠ L ⋅ M (in general)

Proposition 1: Φ ⋅ L = L ⋅ Φ = Φ
Φ ⋅ L = { x ⋅ y | x ∈ Φ and y ∈ L } … will always be false. (Look this up, I didn't get it all down.)

{λ} ⋅ L = L ⋅ {λ} = L

λ ⋅ L is nonsense! Do not write this on an exam!

L^k = L ⋅ L … L (k times)

L⁰ ≡ {λ} by definition
L^k = L
L^{k + 1} = L^k ⋅ L = L ⋅ L^k where k ≥ 0

Φ⁰ = {λ} Here's a case where you do get something for nothing. Through the magic of mathematical definition…

[See slides on Phrase Structure Grammar.]

⇒ : V_G* → V_G*
α ⇒ β iff α = α₁ = α₂
and β = α₁ = α₂
and u → v ∈ G.

Initial state is S, the start symbol. The computer non-deterministically chooses a rule from the grammar which matches the left-hand side and if it finds a match it replaces the occurrence of the left-hand side with the right-hand side…

S = α₀ ⇒ α₁ ⇒ α₂ ⇒ … ⇒ α_∞

Computation continues indefinitely until some case that may terminate it. If the current state of memory happens to be an element of a string over the terminal alphabet (no non-terminals, α_n ∈ Σ*) then the computation halts.

A language defined by G — Let G = (N,Σ,P,S) be a psg. Then the language generated by G is the set: L(G) = { x ∈ Σ* | S ^G⇒ + x }; that is, x ∈ L(G) if and only if there is a computation in G satisfying: S = α₀ ^G⇒ α₁ … ^G⇒ α_n = x, for some n ≥ 1. That's how Chomsky defined a language for a phrase structured grammar.

Type 0: P = { u → v | u ∈ V* N V* and v ∈ V* }

Type 1: P = { u → v | u ∈ V* N V* and v ∈ V* and |v| ≥ |u| } Restriction: no erasing! "Context sensitive."

N = { S, X, Y }
Σ = { a, b, c }
P = {
        1: S → SXY
        2: S → Y
        3: X → aXb
        4: Y → bbY
        5: X → Y
        6: Y → c
        7: aX → Yb
        8: bY → bc

You can replace Y by c but only when preceded by a b (Rule 8). Rules 1-6 are context-free rules. These rules mean that you can replace S regardless of what its context is. There are no constraints on S's context. Rules that have two or more symbols on the left-hand side are context-sensitive.

Type 2: P = { u → v | u ∈ N and v ∈ V* } "Context-free grammar." Erasing is allowed again, but the left part is restricted to be context-free.

Context-free grammars are the family of languages from which we take all programming languages. Programming languages can, then, be described by Type 2 "Context-Free" grammars.

Type 3: P = { u → v | u ∈ N and v ∈ Σ* ∪ Σ*N } "Right linear."

Linear CFG: u → v ∈ P iff u ∈ N and v ∈ Σ* N Σ* ∪ Σ* … It's either a string of terminals or a string that has exactly one non-terminal that can occur anywhere.

Recognizers/Acceptors

x ∈ Σ* → [ P ] → Halt: Accept! if x ∈ L(P). If x ¬sin; L(P) then Halt and Reject. R may never Halt!

Type 0 grammars correspond to Turing Machines. Type 1 correspond to linear bounded automata (memory is bounded by a multiple of the input size. Type 2 correspond to non-deterministic push-down automata (memory must take the form of a stack, unbounded in size but only access the top element). Type 3 correspond to regular, finite-state machines. Finite state machines have a fixed amount of memory for all inputs so there's only a limited amount of information that they can remember.

This course will be structured around showing these equivalencies and showing properties of the individual languages (closed under blah blah) and what can you prove (algorithms) to answer questions?

Example 2

G₂ = { N, Σ, P, S }
N = { S, X }
Σ = { 0, 1 }
P = { 1: S → ₁S
2: S → λ
3: S → ₀X
4: X → ₁X
5: X → ₀S }

This is a context-free grammar.

S ²⇒ λ ∈ Σ* ∴ L(G).

L(G) = { λ …

S ¹⇒ ₁S ¹⇒ ₁₁S ³⇒ ₁₁₀X ^4,4⇒ ₁₁₀₁₁X ⁵⇒ ₁₁₀₁₁₀S ²⇒ 110110 ∈ Σ* ∴ 110110 ∈ L(G)

L(G) = { 1 }* "The set containing 1, star."

L^k
L⁰ = { λ }
L¹ = L
L^k+1 = L^kL = LL^k
L* = ^∞_k=0∪ L^k = L⁰ ∪ L¹ ∪ L² ∪ …
L⁺ = ^∞_k=1∪ L^k

L(G_v) = {1}*({0}{1}*{0}{1}*)* = {1}* = …

Our program produces strings that have an even number of zeros as the output of a computation. We need to show that.

You should always try proof by induction first.

{1}* ( {3} {4}* {5} )* {2}

Every execution sequence that terminates must be of this form. Replace stars by variables and do induction on those variables and show what the properties of the centential form produce.

{1}ⁿ¹ ( {3} {4}ⁿ² {5} )ⁿ³ {2} ⇒ 1ⁿ¹ (0 1ⁿ² 0)ⁿ³ S

You won't be asked to prove this on a quiz or an exam.

Example 3

N = { S }
Σ = { 0, 1 }
P = { 1: S → 0S1
2: S → λ
}

S ²⇒ λ
S ¹⇒ 0S1 ¹⇒ 00S11 ¹⇒ … ¹⇒ 0ⁿS1^{n 2}⇒ 0ⁿ1ⁿ

This cannot be generated by a Type 3 grammar.

A regular grammar can be Type 3, Left-Linear, DFSA, NFSA, or regular expressions.

L = { x ∈ {0,1}* | |x|₀ = |x|₁ } You'll never be able to come up with a finite-state machine that will recognize this language.

Example 5

1: S → SXYZ
2: S → λ
3: YX → XY
4: ZX → XZ
5: ZY → YZ
6: X → a
7: aX → aa
8: aY → ab
9: bY → bb
10: bZ → bc
11: cZ → cc

This looks like Type 1 but erasing is allowed. So it's a Type 0.

S ⇒ SXYZ ⇒ SXYZXYZ ⇒ XYZXYZ ⇒ XXYYZZ (with combination of 3, 4, 5) … You should discover how this happens.

Use 6 a couple times and get ⇒ aaYYZZ

8, 9 ⇒ aabbZZ

10, 11 ⇒ aabbcc

{ aⁿbⁿcⁿ | n > 0 } ⊆ L(G)

Describe as many different kinds of strings as you can that are members of L(G).

Intro to Grammars and Languages

Definition: A alphabet is a finite non-empty set of abstract symbols. We're not going to assign any particular meaning to the symbols other than the identities (hence abstract).

Σ = {0,1}
Δ = {a,b,c}

Definition: Σ* = { x | x is a finite string of symbols composed from Σ }.

A string of length zero (no symbols) is denoted by λ ∈ Σ*

Given x ∈ Σ*, |x| denotes the length of x (number of symbols)

|λ| = 0

For any a ∈ Σ and x ∈ Σ*, |ax| = |a| + |x| = |x| + 1 where |a| = 1 for each a ∈ Σ

Σ = {a,b,c}
Σ* = {λ, a, b, c, aa, ab, ac, ba, bb, bc, cb, cc, ...}

Challenge: write a C program that will enumerate Σ* (spit out the elements of Σ* in that order).

What is the cardinality of Σ? |Σ| = 3

EXAMPLE

What is the cardinality of Σ*? |Σ*| = ?

You must first find a one-to-one and onto function.

f(λ) = 0

You will need a formula to map strings into natural numbers.

Definition: a language, L, over Σ is any subset of Σ*

How many languages are there over Σ? The cardinality of the powerset.

|Σ*| = ℵ₀

|L| > |Σ*|

We express algorithms in programming languages. Programs (e.g. representation of numbers) are descriptions or encodings of algorithms (e.g. natural numbers).

P ∈ L_p ⊆ Σ*_p

P' ∈ {0,1}*
M ∈ {0,1}*

A process is a result of executing (interpreting) a program. A program is a static concept and a process is a dynamic concept.

x ∈ L_input ⊆ Σ*_input
y ∈ L_output ⊆ Σ*_output

f_p : Σ*_input → Σ*_input

The claim is that there is at most a countable number of distinct functions that we can express.

F = { f_p | p ∈ L_p }

What is the cardinality of that set?

|F| ≤ |L_p| ≤ |Σ*_p| = ℵ₀

|ℜ(Σ*) | is uncountable

The Structure of Computable Languages

Family of Computable Languages

The family of all computable languages is recursively enumerable. Noam Chomsky was one of the pioneers of the study of natural language and some important concepts that led to computer science and programming languages. Came up with Phrase Structure Grammar. He developed this mathematical notation… A grammar is really a non-deterministic algorithm. It's a specification (program, computation) that is non-deterministic. Chomsky's notion of Phrase Structure Grammar took a string as input and output a string. It was essentially a string generator.

A phrase structure grammar has five? parts: set of symbols, nonterminal alphabet, terminal alphabet, rules (instructions), and a unique symbol called the start symbol.

G = (N, Σ, P, S)

N: nonterminal alphabet
Σ : terminal alphabet
S ∈ N: start symbol
P: inifinite set (possibly empty) of predictions or (illegible)
P = { u → v | u ∈ V*_GNV*_G and v ∈ V*_G }
The left part has at least one nonterminal

The only way the program can get anywhere is if you have at least one rule in your program S → v until you have eliminated all non-terminals from your computation state. You're left with some string of your terminal alphabet. Once you're in a computation state with no non-terminals, computation halts and none of these rules apply.