COT4210: Course Information

Prerequisites: COT3100 (Discrete Structures), MAC3312 (Calc II)

Assignments: About one every week (due on Thursday of next week). Generally short. You may work in teams of two, unless I say otherwise. Teams turn in only one copy of assignment.

Topics: (Mostly taken from Hein 3.2; 11 - 14; 7 - 9)

 Introduction to formal languages, automata theory and computability theory.

 Emphasis in formal languages is on regular and context free languages.

Regular languages and finite state automata will be related to sequential circuits, lexical analysis, data validation, and state transitions used to solve problems involving complex interactions.

Context free languages and push down automata will be related to parsing of programming languages. In particular, we will study LL and LR parsing.

Computation models will be related to necessary features for a model of computation (e.g., a programming language) to be complete. Limits of mechanical computation will be tied to problems that arise naturally and sometimes ubiquitously.

1. Goals of course; Prerequisites; Rules of game.
2. Some challenges to get your synapse firing.
3. Overview of language construction. (Chapter 3, Section 2)

Language generation and recognition problems. Some notion of complexities.
4. Formal concept of a grammar with simple examples.


Assignment #1 (due September 5): Problems at end of Section 3.2: 1, 2c, 3c, 10, 13, 15.
 
 

1. Grammars and Derivations: More examples of grammars with precise definition of the language associated with a grammar.
2. Meaning and Ambiguity: Distinction between grammar and language or more importantly a family of grammars and the languages its member generate.
3. Sets formed using closure under union, concatenation and star.

 

 

1. Regular expressions and regular sets. (Chapter 11.1). Importance in lexical analysis.
2. Examples of regular expressions and operations on them.
3. Regular equations -- solving recurrence equations.
4. A brief intro to Finite state automata. (Chapter 11.2)


Assignment #2 (due September 12): Problems at end of Section 11.1: 1f, 2h,i, 3, 9a, 10.
Prove that (R+S)* is contained in (R*S*)*, where R and S are regular sets.

1. Recognizers in general; Finite state automata in particular. (Chapter 11.2).
2. Deterministic FSAs -- 5 tuple definition.
1. Odd parity recognizer
2. Proper binary sum recognizer
3. All binary strings that are 1 mod 5
3. Non-deterministic FSAs (note lambda transitions allowed.)
1. All binary strings that are either 1 or 3 mod 5
4. Equivalence of regular sets and finite state languages -- constructive techniques
1. Transforming regular expressions to finite state automata.
2. Transforming finite state automata to regular expressions.

1. Deterministic versus non-deterministic automata. Next state function for DFA; next state relation for NFA.
2. Formal proof that every regular set is accepted by a FSA.
1. Basis: Show FSAs for empty set, {empty string}, {a} where a is in alphabet.
2. Induction: Show if R and S are recognized by fsa then so are
1. R union S
• Machine uses paired states. Accepts if either component is acceptable.
• Prove inductively, based on length of string that this works.
2. R concatenate S
• Machine is easiest to do using non-determinism. Accepts if any path finds the string acceptable.
• Prove inductively, based on length of string that this works.
3. R*
• Show how easy this one is if we use non-determinism.
• This motivates showing non-determinism does not increase power.
Assignment #3 (due September 19): Problems at end of Section 11.2: 5, 6c, 9, 10.

1. Present a detailed formal proof of closure of Determinstic Finite State State Languages under union.
2. Show how easy it is to extend techniques just developed to prove closure of finite state languages under intersection and many other binary operations.
3. Complete closue constructions and proofs based on NFAs.
4. Introduce formal proof that every FSL is regular via an example of the Rijk construction.


Assignment #4 (due September 26): Problems at end of Section 11.3: 3, 11.

IMPORTANT DATES:

• Quiz#1 (Thursday, September 28)
• Exam#1 (Thursday, October 12)
• Withdraw Deadline (Friday, October 20)
• Quiz#2 (Thursday, November 9)
• Exam#2 (Tuesday, November 21)
• Final Exam (Tuesday, December 5, 10:00-12:50)

1. Formal proof that every finite state language is regular. We'll assume automata with no lambda transitions.
1. Define Rijk = { w | automaton, starting in state i with input w, ends up in state j, after having consumed all of w, never visiting any nodes with index higher than k }.
2. Clearly the language recognized is R1nn, where automaton has n states.
3. Show all Rijk, k<=n are regular.
1. Basis: Rii0 contains empty string, for all i.

Rij0 contains b, whenever f(i,b) contains j, where f is the transition function.
2. Induction: Rij(k+1) = Rijk union Ri(k+1)k (R(k+1)(k+1)k)* R(k+1)jk
2. Note that regular equation result provides an alterative proof that every finite state language is regular. Again, we must assume automata with no lambda transitions.
3. Finite automata as output devices: Mealy and Moore Models.
1. Binary sum using Mealy model
2. Binary sum using Moore model

1. Getting rid of lambda transitions in an NFA.
1. Compute lambda-closure for each state.
2. Extend to lambda-closure of a set of state
3. Allow multiple start states (lambda-closure of old start state).
4. Replace transition from p to q on b, by transitions from p to the lambda- closure of q on b.
2. Show proof that lambda-free NFA can be converted to DFA using subsets of the set of original states.
3. Constructing the minimum state DFA for a given finite state language. First show constructive technique from text. This is based on notion of indistinguishable states.


Assignment #5 (due October 3): Problems at end of Section 11.4: 1f, 2h, 3c, 5, 6, 8b (by Lemma 11.13 and 11.14).
Show L = { w w | w is a string over {0,1} } is not recognized by an FSA by showing that its associated right invariant equivalence relation has infinite index.

1. Show matrix technique and discuss its complexity.
2. Notion of a right invariant equivalence relation and its index.
3. Myhill-Nerode Theorem (proof will be later): The following are equivalent.
1. L is accepted by some FSA.
2. L is the union of some of the classes of a right invariant equivalence relation of finite index.
3. The right invariant equivalence relation defined by

xRy iff (for all z) xz is in L just in case yz is in L
has finite index.
4. The index of the relation from part 3 above is the number of states in a minimum FSA. The minimum FSA is unique up to renaming of states.
5. If the index of relation 3 is not finite, then L is not regular.

Review of all material to date in preparation for Quiz#1.
This quiz is based on material from Chapter 3.2 and Chapter 11.1-3.

Major Topics:

• Grammars and Derivations: Context free and regular. Notions of derivation, leftmost derivation, rightmost derivation, ambiguity.
• Regular sets: Sets formed using closure under union, concatenation and star, with empty set, set with empty string, and singleton sets as bases. Regular expressions: Definition and associated regular sets.
• Finite state automata. DFAs and NFAs. Closure of DFA languages under union, intersection and complementation. Closure of NFA under union, concatenation and *. Associating FSAs with REs. Associating a regular expression with an FSA. Proof using Rijk sets from notes. Setting up and solving sets of simultaneous regular equations. Proof of uniqueness of solution to R=Q+RP (where P does not contain the empty string.)
• Moore and Mealy models: Automata with output. Equivalence.
• Epsilon moves: Epsilon closure of a state. Equivalence to non-det.
• Conversion to deterministic FSAs. Formal proof of equivalence.
• Minimization: Process of minimization. Indistinguishable states. Triangular matrix approach. Analysis of cost of different approaches. Constructing the minimum state DFA for a given finite state language.
• Myhill-Nerode Theorem as basis for unique minimum state DFA: Right invariant equivalence relations. Specific relation for a language L. Applications for now -- proof is later.

1. Present two, distinct leftmost derivations of some string produced by the grammar:

S -> XC | AY; X -> aXb | ab; Y -> bYc | bc; A -> aA | a; C -> cC | c
2. Prove, for R, S and T regular expressions, that R + S = R + T does not always imply that S = T.
3. Present an FSA that recognizes the regular language associated with (a+bb)* (b+aa)*
4. Construct a regular expression from some fsa using regular equations. Show all steps. Regular equations might be of form

A = B0 + A(0+1). B = A0. C = B1 + C0, where C is associated with final state.
5. Construct a regular expression from some fsa using Rijk theorem. Show all steps.
6. Construct a regular expression from some fsa using text technique. Show all steps.
7. Prove the correctness and uniqueness of the solution R=QP*, when R = Q+RP, and P does not contain the string of length zero.
8. Produce some FSAs and Mealy machines for specific languages, or translations.
9. Show lambda closures for the states of some NFA. Convert the NFA to an equivalent DFA.
10. Minimize the states of some DFA. Show various techniques.
11. Show RI equivalence classes for some language. Use this to determine whether or not language is regular.
12. Convert between regular grammars are FSAs.
13. Use Myhill-Nerode to show a language is not regular.

1. QUIZ#1

1. Pumping Lemma (weak and strong forms).
2. Formal proof of Pumping Lemma (strong form).

Let L be regular. There exists an N, dependent on L alone, such that, if w is in L and |w| >= N, then w may be written in the form xyz, where |xy| <=N, |y| >0, and for all k gt;= 0, xy^kx is in L.

3. Application of Pumping Lemma, including weak form.
4. Empahsize that the proper application of the Pumping Lemma is an adversarial process
• YOU choose L.
• PL chooses N.
• YOU choose a w in L.
• PL chooses an xyz, such that w=xyz, where |xy| <= N, |y| > 0.
• YOU choose a k such that xy^kx is not in L.
• That's it. You've shown that L is not regular.
5. Challenge questions
• Why is { x x(rev) w | x is not lambda and w is arbitrary} so hard to prove non-regular using the Pumping Lemma, yet so easy using Myhill-Nerode?
• Show { x w x(rev) | x is not lambda and w is arbitrary} is regular.

1. Review of results from Quiz#1 in preparation for Exam#1.
2. Discussion of every problem encountered in first quiz with emphasis on weaknesses that will be tested on exam.

1. Regular Grammars
• Examples
• Equivalence of forms A -> wB; A -> w with A -> aB; A ->a; A -> lambda, and even with A -> aB; A -> lambda.
2. Every FSL is generated by a regular (right linear) grammar.
3. Every regular language can be recognized by a NFA.
4. The left and right linear grammars are equivalent.
5. Three proofs of closure of regular sets under reversal.
6. Major Topics for Exam:
• This exam is based on material from Chapter 3.2 and all of Chapter 11.
• All topics from Quiz#1.
• Pumping Lemma: Weak and strong forms. Proofs and applications.
• Regular grammars: Equivalence with FSAs. Proofs and applications
7. Sample Questions (or forms of questions) for Exam:
1. Those seen in Quiz#1.
2. Prove the correctness and uniqueness of the solution R=QP*, when R = Q+RP, and P does not contain the string of length zero.
3. Convert between regular grammars and FSAs.
4. State, prove and apply strong Pumping Lemma.

1. EXAM#1

1. Proof of Myhill-Nerode Theorem.
2. Significance of Myhill-Nerode for uniqueness of minimum state fsa and for showing certain languages are not regular. Use to solve equivalence problem.

1. Closure of regular languages under substitution, homomorphism and inverse homomorphism.
2. Closures that follow from substitution, homomorphism and inverse homomorphism (e.g., union, concatenation, Kleene *, quotient with regular languages, INIT, LAST, MID).

1. Closure of regular sets under quotient with regular sets.
2. Algorithms for reachable states and states that can reach a point.
3. Decision properties: Emptiness and finiteness.
4. Use of reachability algorithms to solve emptiness and finiteness.
5. Use of Pumping Lemma for emptiness and finiteness properties.


Assignment #6 (due November 2):

1. Use the Pumping Lemma to prove that

{ a^f | f is a member of the Fibonacci sequence} is not regular.
2. Reprove this using the Myhill-Nerode Theorem.
3. Prove that any class of languages containing the finite languages and closed under concatenation, union, *, intersection with regular languages, substitution and homomorphism, is also closed under EXTERIOR, where

EXTERIOR(L) = { xz | xyz is in L, for some y }.

1. Context Free Grammars -- Formal Definition, Basic Concepts and Examples.
2. Parse trees, A-trees. Definition of a parse tree and proof that A =>* X iff there exists an A-tree with X as its yield.
3. Ambiguity and leftmost (rightmost) derivations.
4. Closures under union, concatenation and Kleene *.
5. Pushdown Automata -- Formal Definition, Basic Concepts and Examples.


Assignment #7 (due November 7):

1. Problems at end of Section 12.1: 1f, 2d.
2. Problems at end of Section 12.2: 1e, 2, 4b, 7b, 8.

1. Deterministic versus non-deterministic PDAs.
2. Various notions of acceptance (final state, empty stack, final state and empty stack) and their equivalences.
3. Equivalence of different forms of acceptance.
4. Development of notions of top-down and bottom-up parsing from simulation of CFG by PDA.

1. Notion of an instantaneous description (ID) 
2. Equivalence of Context Free and Push Down languages.
3. More discussion of shift-reduce bottom-up parsing and predictive top-down. Examples of how ambiguity can cause trouble, and how poorly chosen unambiguous grammars can also be annoying.
4. Ambiguous grammars versus inherently ambiguous languages -- the quest for a decidable subset of the unambiguous Context Free grammars.

1. Complete equivalence of PDA to CFG.
2. Reasons to avoid left recursion of top-down and right recursion on bottom up.
3. Left and right recursive rules and how to convert from one to the other.
4. Recursive descent parsing and its aversion to left recursion.
5. Go over assignments as preparation for quiz.

1. Quiz#2 on Chapter 11.4; 12.1, 12.2; some preliminaries on grammar-driven parsing.
2. Guarantees
1. Proofs that some language is not regular -- Pumping and Myhill-Nerode.
2. Proof of one part of Myhill-Nerode.
3. A closure similar to quotient, prefix, etc.
4. Some question concerning decision procedures for regular languages (empty, finite, membership, etc.)
5. Write a CFG for some prescribed language.
6. Construct a PDA from a CFG and/or vice versa.
7. Removal of either left or right recursion.

1. Brief overview of parsing of Deterministic CFLs via LL and LR strategies.
2. Recursive Descent Parsing -- building parser from grammar. Left recursion problem.
3. Reduced grammars (no lambda rules, no unit rules, no useless symbols)

1. More on grammar reductions.
2. Chomsky Normal Form -- conversion algorithm.
3. The Pumping Lemma for CFLs (based on CNF).
4. Strong form versus weak form Pumping Lenna for CFLs.
5. Applying the Pumping Lemma -- a^n b^n c^n.
6. Cocke-Kasami-Younger (CKY): CNF and an order(N^3) parser for arbitrary CFLs.

1. More on Cocke-Kasami-Younger.
2. More applications of Pumping Lemma for CFLs.
3. Greibach Normal Formal -- relation to linear parsing algorithms.
4. Closure of CFLs under intersection with regular (can create machine with paired states), substitution (easy using grammar), reversal (easy using grammar).
5. Consequences of above for quotient with regular, Prefix, Suffix, Interior, Exterior, etc.
6. Non-closure of CFLs under intersection, quotient and complement.
7. Decision problems for CFL's -- emptiness, finiteness, membership.


Assignment #9 (due November 30):

1. Use CKY to show that a+(a)-a is in L, where L is defined by:

E -> a | EY | LZ | PE ; Z -> ER ; Y -> PT; T -> a | LZ ; P -> + | - ; L -> ( ; R -> )
2. Use the Pumping Lemma for CFLs to show L is not context free:

L = { a^i b^j c^k | i,j > 0 and k = i * j }
3. Convert the following to CNF. Show all steps.

S -> A | B ; A -> 1CD | lambda ; B -> 1CE ; C -> 1C1 | 01 ; D -> 0A ; E -> 0B
Assignment #10 (OPTIONAL due December 5):
1. Prove that the grammar { S -> aS | aSbS | lambda } produces

L = { w | w is in {a,b}+, w = xy implies #a's in x >= #b's in x }
2. Prove that the Post Correspondence Problem is solvable when the base alphabet is a single letter.

1. Basic concepts underlying computability theory
• Solved versus solvable problems.
• Unsolved versus unsolvable problems.
• Enumerable (semi-solvable) versus non-enumerable problems.
• Existence of unsolvable problems based on a simple counting argument.
• Proof of unsolvability of halting problem using "diagonalization".
2. Turing machine model of computation -- basic definition and simple examples.
3. Register machine model of computation -- basic definition and simple examples.
4. Overview of equivalence of models.
5. Church-Turing Thesis.

1. Proofs of undecidability using reduction from a known unsolvable problem.
2. Examples of undecidability related to debugging software.
3. The Post Correspondence Problem.
4. Use of PCP to show undecidability of ambiguity and emptiness of intersection problems
5. Discussion of guarantees for final exam:
• Easy:
1. Given a context free language, present a pda or grammar.
2. Minimize an fsa, showing all work.
3. Specify some of the basic computability definitions and relations.
4. Identify the complexities of various decision problems concerning regular and context-free languages.
• Median:
1. Show a language is not regular (context free) using pumping lemma.
2. Show closure or non-closure of languages (regular or CFL) under some operation.
3. Convert grammar to PDA. Convert PDA to grammar.
4. Reduce grammar to CNF.
5. Create CKY recognizer from some CNF grammar.
6. Reduce PCP to ambiguity or intersection of CFGs
• Harder:
1. Show one part of Myhill-Nerode.
2. Prove a specific language is generated by some prescribed grammar.

Final Exam -- A Two Part Exam:

1. Required cummulative part. This emphasizes latter half of course, with definite questions from last 3 weeks of classes.
2. Optional part on same material as Quiz#2. This can be used to improve grade on second quiz.

Topics for First Half of Semester

• Regular Sets
• Regular expressions: Definition and associated languages.
• Finite state automata. Associating FSAs with REs.
• Associating REs with FSAs. Proof using Rijk sets.
• Moore and Mealy models: Automata with output. Basic equivalence.
• Non-determinism: Its use. Conversion to deterministic FSAs. Formal proof of equivalence.
• Lambda moves: Lambda closure of a state. Equivalence to non-det.
• Myhill-Nerode Theorem: Right invariant equivalence relations. Specific relation for a language L. Proof and applications.
• Minimization: Why it's unique. Process of minimization. Analysis of cost of different approaches.
• Regular (right linear) grammars, regular languages and their equivalence to FSA languages.
• Pumping Lemmas: Proof and applications.
• Closure properties: Union, concat, *, complement, reversal, intersection, set difference, substitution, homomorphism and inverse homomorphism, INIT, LAST, MID, EXTERIOR, quotient (with reg. set, with arb. set).
• Algorithms for reachable states and states that can reach a point.
• Decision properties: Emptiness, finiteness, equivalence.

Topics for Second Half of Semester

• Context Free Grammars.
• Leftmost versus rightmost derivations.
• Parse trees, A-trees. Definition of a parse tree and proof that A =>* X iff there exists an A-tree with X as its yield.
• Ambiguity and leftmost (rightmost) derivations.
• Pushdown automata; various notions of acceptance and their equivalences
• Push down languages and their equivalence to CFLs.
• Parsing Techniques: LL (top down) and LR (botom up) parsers
• Reduced grammars
• Keep non-terminal A iff A =>* w for some terminal string w.
• Keep symbol X iff S =>* WXY for some strings W and Y.
• A -> lambda removal.
• Chain (unit) rule removal.
• Chomsky Normal Form.
• Left recursion removal.
• Greibach Normal Form.
• Pumping Lemmas for CFLs.
• Closure of CFLs: Union, concat, *, reversal, substitution, homomorphism and inverse homomorphism, INIT, LAST, MID, EXTERIOR, quotient with reg.
• Decision algorithms: Empty, finite, infinite; CKY for membership.
• Basic concepts underlying computability theory
• Solved versus solvable problems.
• Unsolved versus unsolvable problems.
• Enumerable (semi-solvable) versus non-enumerable problems.
• Existence of unsolvable problems based on a simple counting argument.
• Proof of unsolvability of halting problem using "diagonalization".
• Models of Computation - Basic Definitions and Simple Examples
• Turing machines
• Register machines
• Recursive functions
• Overview of equivalence of models.
• Church-Turing Thesis.
• Proofs of undecidability using reduction from a known unsolvable problem.
• Examples of undecidability related to debugging software.
• The Post Correspondence Problem.
• Use of PCP to show undecidability of ambiguity and emptiness of intersection problems