edu(b)log

On The Exam...

a) Cardinality
b) NFA → DFA
c) DFA Minimization
d) RE → NFA
e) DFA → RE
f) Cross-product Construction for Union, Difference, Intersection of Regular Languages.
g) Design a PDA
h) Design a DPDA
i) Design a RLG or CFG
j) Prove L is not Regular or not Context-free
k) Determine L(M) for a given Turing Machine, M.
l) Formal Definitions of Automata, Grammars, Decision Problem, the Halting-Problem, Decidability.
m) Examples of languages in the Chomsky Hierarchy and other language families we've studied.
o) Turing machine that accepts regular languages

Definitely on the exam:
DFA → transition table (from DFA and M', cross product machine) → reachable states → Cross product construction for union, difference, intersection of regular languages

Myhill-Nerode Theorem
Let L be a regular language. THen the following statements are equivalent.

• L is regular.
• L is the union of some of the equivalence classes of a right-variant equivalence relation of finite index.
• The relation R_L has finite index where (x,y) ∈ R_L iff ∀ z ∈ Σ*[xz ∈ L, iff yz ∈ L]

Normal Forms, Etc.

Quiz #2 will be on Monday, July 17.

Topics:

• Closure ops for regular languages
• Pumping lemma and non-regular languages
• Context-free grammars, operator grammars
• Linear CFG
• Normal forms
• Pushdown automata
• Equivalence between PDA and CFG

Definition of an unambiguous context-free grammar: A CFG, G = (N, Σ, P, S), is said to be unambiguous if and only if for every x ∈ L(G) x has a unique leftmost derivation (rightmost derivation) (syntax tree).

Example

P = {1: S → aX
2: X → bbY
3: Y → λ
4: S → abb }

This is ambiguous. There may be many unambiguous grammars for the same language; there may be many ambiguous grammars also. So it is a property of the grammar and not the language.

Theorem. Known families of unambiguous grammars include:

• Operator Precedence
• LR(k) Grammars (k ≥ 0) → YACC → Deterministic Bottom-up Parser Par L(G) in C code.
• LL(k) Grammars (k ≥ 1)

Bottom-up implies the reverse of a rightmost derivation.

Top-down implies a leftmost derivation. *LL(k)

The difference between an unambiguous grammar and an unambiguous language… A context-free language L is said to be inherently ambiguous if and only if for every context-free grammar, G, such that L(G) = L; G is ambiguous. Huh?

Example

L = { aⁿb^mc^k | n = m OR n = k }.

Claim: L is inherently ambiguous.

P = { 1: S → XC
2: S → AY
3: C → Cc
4: C → λ
5: A → aA
6: A → λ
7: X → aXb
8: X → λ
9: Y → bYc
10: Y → λ
}

aabbcc can be formed by two distinct leftmost derivations… So it is ambiguous.

Normal Forms of CFG

Normal forms have some nice properties that make proofs about grammars and context-free languages much easier.

Examples:

1. Reduced normal form
2. Lambda-free context free grammar (no λ rules allowed)
3. Unit-free normal (no X → Y rules)
4. Greibach normal form (X → aY₁Y₂ … Y_n …) ⇒ There exists a recursive descent (top-down parser) for every CFL.
5. Chomsky Normal Form — Every CFL (without λ) has a grammar in Chomsky normal form (every CFL without λ can be parsed with a CNF grammar in O(n³), where n = |x|):
   • X → YZ
   • X → a

Definition:

Let G = (N, Σ, P, S) be a CFG. A rule k: X → w is said to be useless iff:

(a) ∀ π ∈ P*, S ⇒ α implies α ≠ uXv, for any u, v ∈ V_G*. (X is unreachable)

(b) ∀ π ∈ P*, w ⇒ β implies β ∉ Σ* (w is non-terminating).

Theorem. Every CFG, G = (N, Σ, P, S) is equivalent to a grammar, G' = (N', Σ, P', S), where G' has no useless rules. Furthermore N' ⊆ N and P' ⊆ P.

Algorithm for RNF

Step 1: Eliminate non-terminating rules (type b)
Step 2: From the result of Step 1, eliminate all unreachable rules (type a)

Step 1 (Detail):

1.1
Q₀ = { X → w | X → w ∈ P and w ∈ Σ* } (immediately terminating)
Z₀ = { X ∈ N | X appears as a left part in Q₀ }

1.2
Q_k+1 = Q_k ∪ { X → w ∈ P | w ∈ (Σ ∪ Z_k)* }
Z_k+1 = Z_k ∪ { left parts of rules in Q_k+1 − Q_k }

1.3
If (Q_k+1 − Q_k ≠ Φ) then { k+1; goto 1.2 } Else Halt.

1.4
Z_k = The set of all terminating non-terminals
Q_k = The set of all terminating rules in G.
If S ∉ Z_k then L(G) = Φ and G' = ({S}, Σ, &Phi, S). Else G₁ = (Z_k, Σ, Q_k, S), S ∈ Z_k.

Step 2 (Detail):

Begin with G₁ = (N₁, Σ, P, S) where N₁ ⊆ N and P₁ ⊆ P and all rules of G₁ are terminating.

2.1
Zsub>0 = {S} and Q₀ = { S → w | S → w ∈ P₁ }

2.2
Z_k+1 = Z_k ∪ { Y | Y appears in the right part of some rule in Q_k }.
Q_k+1 = Q_k ∪ { Y → w ∈ P₁ and Y ∈ Z_k+1 }.

2.3
If (Z_k+1 − Z_k ≠ Φ) Then { k++; goto 2.2 } Else Halt! G' = (Z_k, Σ, Q_k, S).

Example

N = { S, A, B, C, X, Y, Z } Σ = {a, b}

P = { 1: S → aSX
2: S → AB
3: X → Y
4: Y → bY
5: Y → ZX
6: Z → aa
7: Z → λ
8: A → Cb
9: C → B
10: B → BCa
11: B → λ
}

Step 1:

Q₀ = {6, 7, 11} Z₀ = {B, Z}
Q₁ = Q₀ ∪ {9} = {6, 7, 9, 11} Z₁ = {B, C, Z}
Q₂ = Q₁ ∪ {8, 10} = {6, 7, 8, 9, 10, 11} Z₂ = {A, B, C, Z}
Q₃ = Q₂ ∪ {2} Z₃ = {S, A, B, C, Z}
Q₄ = Q₃ ∪ {} Z₄ = Z₃ (end of step 1).

P₁ = { 2: S → AB
6: Z → aa
7: Z → λ
8: A → Cb
9: C → B
10: B → BCa
11: B → λ
}

Step 2:

Z₀ = {S}, Q₀ = {2}
Z₁ = {S, A, B}, Q₁ = {2, 8, 10, 11}
Z₂ = {S, A, B, C}, Q₂ = {2, 8, 9, 10, 11}

Done… Our reduced grammar is then:

G' = ({S, A, B, C}, Σ, {2, 8, 9, 10, 11}, S)

Parsers

Announcements

Problem Sessions:

Thursday 6:30pm, CSB 232
Saturday 10:00am, CSB 221

Exams are not graded yet, but the solution key is posted on the website.

The next problem set (#4) has been posted.

Lecture

Context-Free Grammars & Languages

The syntax of programming languages is typically defined by context-free grammar.

Recall the definition of a context-free grammar… A 4-tuple, G = (N, Σ P, S), where P = { u → v | u ∈ N and v ∈ V_G* } and V_G = N ∪ Σ. Rules in a context-free grammar have a single non-terminal on the left-hand side. You can apply the rule regardless of the context. The right-hand side can be any string including the null string. It does allow erasing rules. (Type-2 Chomsky).

Example

G = (N, Σ, P, S) where
N = {S, T, F, X},
Σ = {n, v, (, ), +, -, *, /}, and…

P = {1: S → S + T
2: S → S - T
3: S → T
4: T → T * F
5: T → T / F
6: T → F
7: F → -X
8: F → X
9: X → n
10: X → v
11: X → (S) }

L(G) = The language of all expressions over the operator set (+, -, *, /} and operand set {n, v}. G is an example of an unambiguous grammar.

G is an example of a weak-precedence grammar and also an LR(1) grammar.

      v * (n + v)

Top-Down Parse:
S → T
(4) → T * F
(6) → F * F
(8) → X * F
(10) → v * F
(8) → v * X
(11) → v * (S)
(1) → v * (S + T)
(3) → v * (T + T)
(6) → v * (F + T)
(8) → v * (X + T)
(9) → v * (n + T)
(6) → v * (n + F)
(8) → v * (n + X)
(10) → v * (n + v)

There are two passing strategies: Top-Down Algorithms and Bottom-Up Algorithms. Top-Down simulates a left-most in the grammar, G. Bottom-Up is similar to the reverse of a rightmost derivation. You go from the program to the source.

Parse tree for n * v + n:

                    S
                   /|\
                  S + T
                  |   |
                  T   F
                 /|\  |
                T * F X
                |   | |
                F   X n
                |   |
                X   v
                |
                n

leftmost derivation = 1 3 4 6 8 9 8 (10) 6 8 9 rightmost derivation (postorder) = 6 8 9 3 3 4 8 (10) 6 8 9

The bottom-up parser produces a parse by using the stack exactly oriented the other way.

Bottom-up parse of n * v + n:

Split stack into two halves to reverse 9, 8, and 6:

   n | * v + n
   X | * v + n
   F | * v + n
   T | * v + n

T and * appear in the same rule (and v is an operand) so it will shift the * onto the stack:

   T * v | + n
   T * X | + n
   T * F | + n
   T     | + n
   S     | + n

S and + can appear together so the stack shifts, and n is an operand so that shifts…

   S + n | EOF
   S + X | EOF
   S + F | EOF
   S + T | EOF
   S     | EOF

When the stack contains only the start symbol and all that is left is EOF you're done.

DEFINITON_

Let G = (N, Σ, P, S) be a Context-Free Grammar. G is said to be unambiguous if and only if one of the following is true for every x ∈ L(G).

(a) x has a unique leftmost derivation
(b) x has a unique rightmost derivation
(c) x has a unique syntax tree (or parse tree)

All three of the above are equivalent definitions of an unambiguous grammar.

If there is ONE string in the language that has two distinct leftmost or rightmost derivations or syntax trees, it's not unambiguous.

There does not exist an algorithm for determining whether or not a context-free grammar does exist. You can identify specific examples that show a grammar is ambiguous, but there's no algorithm to determine whether something is or is not ambiguous.

Precedence grammars and LR(1) Grammars (recognized by Yacc) are unambiguous. You can prove that every LR(1) grammar and every Precedence grammar is unambiguous.

Operator Precedence Grammar

Specify the generator set = Binary { +, -, *, / } ∪ Unary { !, −, ~ }
The set of Operands = { x, y }

Precedence classes
P₁ <⋅ P₂ <⋅ … <⋅ P_n
Binary <⋅ Unary (General Principle)

B { +, - } <⋅ B { *, / } <⋅ { !, −, ~ }

Binding Strength… * has more binding strength than + so multiplication operations will be interpreted first.

n + v - n

Here we have two operators with the same precedence class. Rules of associativity resolve operators in the same precedence class.

For Binary operators: Left-associative, right-associative, or non-associative.

For Unary operators: Prefix operators ⇔ Right-associative, Postfix ⇔ Left-associative.

EXAMPLE_

{ AND, OR } (Left-Associative) → S
<⋅ { NOT } (Non-Associative) → X
<⋅ { <, >, = } (Non-Associative) → Y
<⋅ { +, − } (Left-Associative) → Z
<⋅ { *, / } (Left-Associative) → A
<⋅ { − } (Non-Associative) → B
<⋅ { operands } → C

Operands always have the highest precedence because an operand can always be a parenthesized sub-expression.

Chaining a bunch of negations together will force someone to put parentheses together. If you don't, you have to count.

The non-terminal for the lowest precedence class will be the Start symbol. They are already labeled above.

Left-associativity ⇒ Left Recursive Rule
Right-associativity ⇒ Right Recursive Rule
Non-associativity ⇒ Non Recursive.

N = { S, X, Y, Z, A, B, C }
P = { 1: S → S and X
2: S → S or X
3: S → X
4: X → not Y
5: X → Y
6: Y → Z < Z
7: Y → Z > Z
8: Y → Z = Z
9: Y → Z
10: Z → Z + A
11: Z → Z − A
12: Z → A
13: A → A * B
14: A → A / B
15: A → B
16: B → −C
17: B → C
18: C → x
19: C → y
20: C → (S) }

You can prove that such a grammar is a precedence grammar and therefore unambiguous. You can parse this grammar in O(n) time where n is the length of the expression.

Come up with the parse tree for this:

not(−x+y)*x>y-z AND x

Regular Expressions

Help session for Test #2 will be Saturday from 1-3pm. Another will be Tuesday from 6-8pm in the same room as before (CSB 232 right across from Dr. Workman's office).

Definition: A regular expression over alphabet Σ is an element of E(Σ) ⊆ (Σ')* where Σ' = Σ ∪ { φ, λ, (, ), ⋅, +, * }

E(Σ) is defined inductively by:

Basis(R₀): Σ ∪ { λ, φ } ⊆ E(Σ).

Inductive Rules:
[1] if e ∈ E(Σ) then (e)* ∈ E(Σ)
[2] if e,f ∈ E(Σ) then (e⋅f) ∈ E(Σ)
[3] if e,f ∈ E(Σ) then (e+f) ∈ E(Σ)

Completion Rule:
Nothing ∈ E(Σ) that cannot be obtained by finite application of above rules.

L[] : E(Σ) → 2^Σ*
(where 2^Σ* is the collection of all subsets of Σ*; all languages over Σ).

L[] is defined recursively as follows:

[0]: L[φ] = Φ = {} (empty set)!
     L[λ] = {λ} (set containing null string).
  &4all; a ∈ Σ[ L[a] = {a} ]
[1] if e ∈ E(Σ) and e = (f)*, where f ∈ E(Σ) 
    then L[e] = L[f]*
[2] if e ∈ E(Σ) and e = (f⋅g), where f, g ∈ E(Σ)
    then L[e] = L[f]L[g] (set concatenation)
[3] if e ∈ E(Σ) and e = (f+g), where f, g ∈ E(Σ)
    then L[e] = L[f] ∪ L[g]

In effect, all of these rules give you the parsing algorithm. Take an arbitrary string over the meta alphabet and if it begins with the left parent and ends with a right parent asterisk then you recursively parse what's in between. If you're able to end up with an expression in one of the forms in the recursive definition then it's a member of the set.

Example 1

L[(φ)*] = L[φ]*

Left side = e; Right side = f

Apply rule zero…

= Φ* = {λ} (the set containing the null string)

Example 2

L[ ((φ + ((a⋅b))*)⋅φ) ] = L[f]L[g] (Rule 2)
f = (φ + ((a⋅b))*)
g = φ

… = L[f] ⋅ Φ = Φ

So any time we concatenate any expression with Φ (the empty set), e ⋅ φ ⇒ φ

Remember that e ⋅ λ = e! So λ and &phi are NOT the same thing.

Example 3

L[ ((φ)* + (a⋅λ)) ] = L[f] ∪ L[g]
f = (φ)
g = (a⋅λ)

… = {λ} ∪ L[g]
L[ (a⋅λ) ] = L[a]L[λ] = {a}{λ} = {a}

… {λ} ∪ L[g] = {a,λ}

Theorem: Let e ∈ E(Σ), for some alphabet Σ, then L[e] is a Regular Language over Σ.

Proof will be by induction on #(e) ≡ The number of occurrences of { +, ⋅, * } in e.

|e|_{+,⋅,*} = #(e)

Basis(#(e) = ∅)
∴ e ∈ Σ ∪ {λ, φ}

L[φ] = Φ

L[λ] = { λ }

L[a] = { a }

a ∈ Σ

Induction Hypothesis: for some m ≥ 0, #(e) ≤ n implies L[e] is Regular.

Consider e ∈ E(Σ) such that #(e) = n + 1

(a) e = (f)*, for some f ∈ E(Σ), #f = n

(b) e = (f ⋅ g), for some f,g ∈ E(Σ), where #(f) + #(g) = n

(c) e = (f + g), for some f,g ∈ E(Σ)(, where #(f) + #(g) = n

Proof:

(a) L[e] = L[f]* = ∪L[f]^k ∪ L[f] ∪ L[f]² ∪ … ∪ L[f]^k

Since #(f) = n, by our Induction Hypothesis, L[f] is Regular.

and L[M'] = L[e]

(b) L[e] = L[f]L[g] = { xy | x ∈ L[f] and y ∈ L[g] }

By I.H. L[f] and L[g] are Regular.

(c) L[e] = L[f] ∪ L[g]
#(f) + #(g) = n

By I.H. L[f], L[g] are Regular.

Corollary: Regular Languages are closed under kleene-*, Union, Concatenation.Theorem 2: Let R ⊆ Σ* be Regular, Then R = L[e] for some e ∈ E(Σ).

Example 4

R₁ = {λ} ∪ R₁{a} ∪ R₃{b}

e₁ = λ + (e₁⋅a) + (e₃⋅b))

e₁ = λ + e₁a + e₃b

e₂ = e₁b + e₄a

e₃ = e₂a + e₄b

e₄ = e₂b + e₃a

e_M = (e₂ + e₄)

Lemma: Let X, A, B be arbitrary subsets of Σ* such that λ ∉ A.

The set equation: X = XA ∪ B has a unique solution X = BA*

A = {a, bb}
B = {λ, b}

X = X⋅A ∪ B

If we have a union then it means B must be a subset of X. XA must also be a subset of X.

B ⊆ X
BA ⊆ X
BA² ⊆ X

∴ X = ∪(k=0 → ∞) BA^k = BA*

Remember this requires the assumption that λ ∉ A.

If you have a Regular equation of the form e = e⋅a + b, λ ∉ L[a] then e = ba*.

So if you get a recursive equation like that you have a solution provided λ ∉ L[a]. Otherwise use plain substitution with string arithmetic.

e₁ = e₁a + (e₃b + λ)
e₁ = (e₃b + λ)a* = e₃ba* + a*

e₂ = (e₃ba* + a*)b + e₄a = e₃ba* + a*b = e₄a
e₃ = e₂a + e₄b
e₄ = e₂b + e₃a

e₂ = ((e₂a + e₄b)ba*b + a*b + e₄a)a + e₄b

e₄ = e₂b + (e₂a + e₄b)a = e₂b + e₂aa + e₄ba = … sorry.

You should wind up with

e₄ = e₂(b + aa)(ba*)

e₂ = e₂aba*ba + e₂(b + aa)(ba)*(bba*ba + aa + b) + a*ba
e₂ = e₂[aba*ba + (b + aa)(ba)*(bba*ba + aa + b)] + a*ba
e₂ = a*ba[aba*ba + (b + aa)(ba)*(bba*ba + aa + b)]*

Hmmmmm, great there is a mistake. Ignore.

Exam: What to expect

• Same type of problems on quiz 1
• converting nfas, r/l linear grammars, regular expressions, etc.
• problem set 3

Oh, who needs titles

DFA Minimization Algorithm

Let M = ( Q, Σ, δ, q₀, A ) be ∈ DFA.

Step 1: Remove all unreachable states.
Result: M₁ = (Q, Σ, δ, q₀, A₁ )
Q ⊆ Q₁, A₁ ∈ A.

Step 2: Check for special cases:

(a) Q₁ = A₁
(b) A₁ = Φ

Step 3: Q₁ ≠ A₁, and A₁ ≠ Φ
Q₁ - A₁ ≠ Φ

Compute ≡ on M₁ = (Q₁, Σ, δ, q₀, A₁)

M_L is defined by the equivalnce class with respect to ≡.

Regular Expressions

Definition: A regular expression e over alphabet Σ.

e ∈ ℜ_Σ ⊂ (Σ')* where Σ' = Σ ∪ { +, -, *, (, ), } ∪ { λ, φ }

Basis: λ, φ ∈ ℜ_Σ and Σ ⊆ ℜ_Σ.

Inductive Rule:
R1: if e ∈ ℜ_Σ then (e)* ∈ ℜ_Σ
R2: if e, f ∈ ℜ_Σ then (e ⋅ f)* ∈ ℜ_Σ
R3: if e, f ∈ ℜ_Σ then (e + f)* ∈ ℜ_Σ

Examples: Σ = {a, b} Σ' = {a, b, λ, &phi, +, ⋅, *, (, ) }

Basis: λ, φ, a, b, ∈ ℜ_Σ

R1: (λ)*, (φ)*, (a)*, (b)* ∈ ℜ_Σ
R2: ... I'm not copying that, sorry.

Is ((a)) ∈ ℜ_Σ?
No. In order to have parentheses, you must have a ⋅ operator.

Is )aλ ∈ ℜ_Σ
No...

So some strings are regular expressions and some are not.

See if you can find a type-2 context free grammar that defines the same language.

G = (N, Σ', P, S)

Σ' = {a, b, λ, φ, +, ⋅, *, (, ) }
N = { S, T, F, X }
P = {
1: S → a
2: S → b
3: S → λ
4: S → φ
5: S → (S)*
6: S → (S⋅S)
7: S → (S + S)
}

Quiz Review Sessions

There will be quiz review sessions on Thursday 6-8pm and Friday 4-6pm most likely in CSB 232 (check the course website for confirmation). If you can't make either time, you should arrange to have your questions answered before the quiz…

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.