COSC-30053 Automata and Language Theory Past Paper PDF

Automata and Language Theory Compiled by: Ria A. Sagum  To the Readers This module was based on the book of Alfred Aho and lecture notes of Dr.Kaishan Fernandez,DLSU 1999. Students are expected...

Automata and Language Theory Compiled by: Ria A. Sagum  To the Readers This module was based on the book of Alfred Aho and lecture notes of Dr.Kaishan Fernandez,DLSU 1999. Students are expected to read the book of Aho to fully understand the discussion. They are also encouraged to use/watch different tools and videos in every topic. R.A.S.  Table of Contents 1. Review of Mathematical Concepts. Strings and Languages ________________________1 1.1 Sets, relations, strings and string operations 1.2 Operations on languages 2. Fundamentals Ideas and Models Underlying Computing Finite Automata and Regular Expression 2.1 Finite State Machines and Finite Automata ___________________________ 8 2.2 Deterministic Finite Automata (DFA) _______________________________ 10 2.3 Non-Deterministic Finite Automata (NFA) ___________________________ 12 2.4 Equivalence of DFA and NFA _____________________________________12 2.5 Finite Automata with ε- Moves (NFA-ε) ______________________________14 2.6 Equivalence of NFA and NFA-ε moves ______________________________15 2.7. Regular Expression and Regular Language __________________________19 2.8. Equivalence of Finite Automata and Regular Expression _________________19 2.9. Finite Automata with Output _______________________________________ 26 3. Properties of Regular Sets 3.1 The pumping Lemma for Regular Sets _______________________________30 3.2 Closure Properties of Regular Sets __________________________________31 3.3. Equivalence and Minimization of Finite Automata _______________________36 4. Context Free Grammars ____________________________________________________41 4.1. Derivation Trees _________________________________________________43 4.2 Chomsky Normal Form ___________________________________________47 4.3 Greibach Normal Form ___________________________________________48 4.5 The existence of inherent ambiguous CFL ____________________________52 5. Pushdown Automata and Context Free Language 5.1. Informal and Formal Definitions ___________________________________ 56 5.2. Equivalence of pushdown automata and CFLs _______________________ 60 6. Turing Machine 6.1. Turing machine Models _________________________________________ 67 6.2. Techniques for TM construction __________________________________ 68 6.3. Variants of Turing Machines _____________________________________ 72 7. Term Project Checking Guide ___________________________________________78 I. REVIEW OF MATHEMATICAL CONCEPTS, STRINGS AND LANGUAGES Overview: This will allow students to review the mathematical concepts that are related to the course. Objectives: The students at the end of this topic will: 1. Recall different mathematical concepts needed for the course. 2. Explain each mathematical concepts. Sets – Definition A set is an unordered collection of objects S = {a, b, c} a, b, c are elements or members of the set S Elements in a set need have no relation to each other S1 = {1, 2, 3} S2 = {red, farmhouse, _, -32} Sets can contain other sets as elements S1 = {3, {3, 4}, {4, {5, 6}}} S2 = {{1, 2}, {{4}}} Set Theory & Proof Techniques Sets do not contain duplicates NotASet = {4, 2, 4, 5} Set – Cardinality Cardinality of a set is the number of elements in the set |{a, b, c}| = 3 |{{a, b}, c}| = 2 ({a, b} and c) Sets – Empty, Singleton Empty Set: {} or ;, |{}| = |;| = 0 Singleton set – set with one element {1} {4} {} NO! Set contains 0 elements {{}} {{3, 1, 2}} 1|Page Sets – Membership Set membership: x 2 S 3 2 {1, 3, 5} a 2 {b,c, d} 3 2 {1, {2, 3}} ? {} 2 {1, 2, 3} ? {} 2 {1, {}, 4} ? Sets – Describing Referring to sets List all members {3, 4, 5}, {0, 1, 2, 3, …} S = {x : x has a certain property} S = {x | x has a certain property} S = {x : x 2 N^ x < 10} N is the set of natural numbers {0, 1, 2, …} S = {x : x is prime} A [ B = {x : x 2 A _ x 2 B } A \ B = {x : x 2 A ^ x 2 B} A – B = {x : x 2 A ^ x 62 B} Sets – More Union & Intersection A and B are disjoint if A \ B = {} S is a collection of sets (sets of sets) SS = {x : x 2 A for all A 2 S} S{{1,2}, {2,3}} = {1,2,3} TS = {x : x 2 A for all A 2 S} T{{1, 2}, {2, 3}} = {2} Sets – Subset Subsets & Supersets A is a proper subset of B, A _ B if: A _ B ^ (9x, x 2 B ^ x 62 A) {} is a subset of any set (including itself) {} is the only set that does not have a proper subset 2|Page Sets – Power Set Power set: Set of all subsets 2S = {x : x _ S} 2{a,b} = {{}. {a}, {b}, {a,b}} 2{} = {{}} |2S| = 2|S| Sets – Partition _ is a partition of S if: _ _ 2S {} 62 8(X, Y 2 _), X 6 = Y = ) X \ Y = {} S_ = S {{a, c}, {b, d, e}, {f}} is a partition of {a, b, c, d, e, f} {{a, b, c, d, e, f}} is a partition of {a, b, c, d, e, f} {{a, b, c}, {d, e, f}} is a partition of {a, b, c, d, e, f} Ordered Pair (x, y) is an ordered pair Order matters – (x, y) 6 = (y, x) if x 6 = y Hence ordered x and y are the components of the ordered pair (x, y) Cartesian Product Why “Cartesian”? Think “Cartesian Coordinates” (standard coordinate system) R X R is the real plane Set of all points (x, y) where x, y 2 R R is the set of real numbers (think “floats” if you’re CS) Cartesian Product Can take the Cartesian produce of > 2 sets? A x B x C = {(x, y, z) : x 2 A, y 2 B, z 2 C} {a} x {b, c} x {d} = {(a, b, d), (a, c, d)} (Technically, A x B x C = (A x B) x C) {a} x {b, c} x {d} = {((a, b), d), ((a, c), d)} Often drop the extra parentheses of readability 3|Page Relations A relation R is a set of ordered pairs For example the relation < over the Natural Numbers is the set: { (0, 1), (0, 2), (0, 3), … (1, 2), (1, 3), (1, 4), … (2, 3), (2, 4), (2, 5), … …} Relations Often, relations are over the same set That is, a subset of A x A for some set A Not all relations are over the same set, However, Relation describing prices of computer components {(Hard drive, $55), (WAP, $49), (256M DDR, $44), …} Functions A function is a special kind of relation (all functions are relations, but not all relations are functions) A relation R _ A x B is a function if: For each a 2 A, there is exactly one ordered pair in R with the first component a Functions A function f that is a subset of A x B is written: f: A 7! B (a, b) 2 f is written f(a) = b A is the domain of the function If A0 _ A, f(A0) = {b : a 2 A0 ^ f(a) – b} is the image of A0 The range of a function is the image of its domain. A function f : A 7! B is: one-to-one if no two elements in A match to the same element in B onto each element in B is mapped to by at least one element in A a bijection if it is both one-to-one and onto the inverse of a binary relation R _ A x B is denoted R – 1, and defined to be {(b, a) : (a, b) 2 R} A function only has an inverse if … Relation Types A relation R _ A x A is reflexive if (a, a) 2 R for each 2 A 4|Page  8(a 2 A), (a, a) 2 R Each node has a self loop ab cd ab cd Reflexive Not Reflexive A relation R _ A x A is symmetric if (a, b) 2 R whenever (b, a) 2 R (a, b) 2 R = ) (b, a) 2 R Every edge goes “ both ways” ab cd ab cd Symmetric Not Symmetric A relation R _ A x A is antisymmetric if whenever (a, b) 2 R, a, b are distinct (b,a) 62 R (a, b) 2 R ^ a 6 = b =) (b, a) 62 R No edge goes “both ways” ab cd ab cd Antisymmetric Not Antisymmetric Can a relation be neither symmetric nor antisymmetric? A relation R _ A x A is transitive if Whenever (a, b) 2 R, and (b, c) 2 R, (a, c) 2 R (a, b) 2 R ^ (b, c) 2 R =) (a, c) 2 R Every path of length 2 has a direct edge ab cd ab cd Transitive Not Transitive Closure 5|Page  A set A _ B is closed under a relation R _ ((B x B) x B) if: a1, a2, 2 A ^ ((a1, a2), c) 2 R =) c 2 A That is, if a1 and a2 are both in A, and ((a1, a2), c) is in the relation, then c is also in A N is closed under addition N is not closed under subtraction or division Relations are also sets (of ordered pairs) We can talk about a relation R being closed over another relation R0 Each element of R0 is an ordered triple of ordered pairs Example: R_AxA R- = {(((a, b), (b, c)), (a, c)) : a, b, c 2 A} If R is closed under R0, then … Reflexive closure of a relation R _ A x A is the smallest possible superset of R which is reflexive Add self-loop to every node in relation Add (a, a) to R for every a 2 A Transitive Closure of a relation R _ A x A is the smallest possible superset of R which is transitive Add direct link for every path of length 2. 8(a, b, c 2 A) if (a, b) 2 R ^ (b, c) 2 R add (a, c) to R Relation Types Equivalence Relation Symmetric, Transitive, Reflexive Examples: A is the set of English words, (w1, w2) 2 R if w1 and w2 start with the same letter Three basic proof techniques Induction Contradiction Pigeonhole Principle Alphabets & Strings An alphabet _ is a finite set of symbols _ 1 = {a, b, …, z} _2 = {0, 1} A string is a finite sequence of symbols from an alphabet fire, truck are both strings over {a, …, z} length of a tring is the number of symbols in the string |fire| = 4, |truck| = 5 The empty string _ is a string of 0 characters 6|Page  |_| = 0 _ is the concatenation operator w1 = fire, w2 = truck w1 _ w2 = firetruck w2 _ w1 = truckfire w2 _ w2 = firefire Often drop the _: w1w2 = firetruck For any string w, w _ = w Concatenation & Reversal We can concatenate a string with itself: w1 = w w2 = ww w3 = www By definition, w0= _ Can reverse a string: wR truckR = kcutr Formal Language A formal language (or just language) is a set of strings L1 = {a, aa, abba, bbba} L2 = {car, truck, goose} L3 = {1, 11, 111, 1111, 11111, …} A language can be either finite or infinite Language Concatenation We can concatenate languages as well as strings L1L2 = {wv : w 2 L1 ^ v 2 LR} {a, ab}{bb, b} = {abb, ab, abbb} {a, ab}{a, ab} = {aa, aab, aba, abab} {a, aa}{a, aa} = {aa, aaa, aaaa} {} is the empty language {_} is the trivial language Kleene Closure (L _) 7|Page 2. FUNDAMENTALS IDEAS AND MODELS UNDERLYING COMPUTING FINITE AUTOMATA AND REGULAR EXPRESSION Overview: In this topic the basic knowledge in the computing models will be discussed these are the finite automata and regular expression Objectives: At the end of the topic the students will be able to: 1. Explain the difference and equivalence of the Finite Automata Models. 2. Design a Finite Automaton model given a problem. 3. Simulate how strings are being accepted by different FA models. 4. Explain how to convert one model to another model. 2.1 Finite State Machines and Finite Automata THEORY OF AUTOMATA deals with different properties of mathematical models. These models play a role in several applied areas of Computer Science. One model called FINITE AUTOMATON, is used in text processing, compilers and hardware design. Another model, called the CONTEXT-FREE GRAMMAR, is used in programming languages and AI. An excellent place to begin the study of the theory of computation. The theories of computability and complexity require a precise definition of a computer. Allows practice with formal definition of computation as it introduce concepts relevant to other non-theoretical areas of Computer Science. Finite State System The finite automaton is a mathematical model of a system, with discrete inputs and outputs. The system can be in any one of a finite number of states. The states of the system summarize the information concerning past inputs that is needed to determine the behavior of the system on subsequent inputs. The mechanism does not remember all the previous inputs, only the current state and the current input. Example: A man with a wolf, goat, and cabbage is on the left bank of a river. There is a boat large enough to carry the man and only one of the other three. The man and his entourage wish to cross to the right bank, and the man can ferry each across, one at a time. 8|Page  However, if the man leaves the wolf and goat unattended on either shore, the wolf will surely eat the goat. Similarly, if the goat and cabbage are left unattended, the goat will eat the cabbage. Is it possible to cross the river without the goat or cabbage being eaten? 9|Page 3.2 DETERMINISTIC FINITE AUTOMATA Definition A deterministic finite automaton (DFA) M can be specified by a quintuple (Q, ∑, δ, s, F) where − Q is an alphabet of state symbols. ∑ is a alphabet of input symbols. δ is the transition function where δ: Q × ∑ → Q s in Q is the start state (F ⊆ Q) is a set of final state/states. Input Tape Start Start state Final state/accepted state a Transition by reading input a Example: DFA DFA Definition 1. 0 1 0, 1 M = (Q, ∑, δ, s, F) Q = {A, B, C} S 1 0 A B C ∑ = {0, 1} s=A F ={A, B} 10 | P a g e Transition Table: Note: δ 0 1 This table summarizes the transition of the graph (δ: Q × ∑ → Q), such ->*A A B that for a current state given an input will moved to a state. *B C B Example, current state is A with an input of 0 will go to state A, and if the C C C current is A with an input of 1 will go to state B. Questions: Given strings below, put a check if the string is accepted and cross otherwise. Please note that a string will be accepted if after reading all the input, one character at a time, the state it will be in is a element of the set of Final States (F ⊆ Q). String Acceptance 1. 1101 2. 011 3. 110 4. 00001 It will be very easy to know if the string is accepted or rejected by simulating the reading of the string in the graph, but then, the answer must be mathematically acceptable, therefore, the solution must be presented in order to state that such string is accepted or not. To formally describe the behavior of FA on a string, we must extend the transition function δ to apply to a state and a string rather than a state and a symbol. We define a function ^ δ from Q x ∑* to Q. The intention is that δ(q,w) is the state the FA will be after reading w starting in state q. Put another way, δ(q,w) is the unique state p such that there is a path in the transition diagram from q to pe, labeled w. Formally we define 1) δ (q,ε) = q, and 2) for all strings w and input symbols a, δ(q,wa) = δ(δ(q,w),a). Thus, a string x is said to be accepted by a finite automaton M = (Q, ∑, δ, s, F) if δ(q0,x) = p for some p in F. The language accepted by M, designated L(M), is the set {x| δ(q0,x) is in F}. Suppose we would like to know if 101(x) is accepted by the given automaton (Example DFA) M. We note that δ(A,1) = B, and δ(B,0) = C, and δ(C,1) = C, thus, δ (A,101)= δ(δ(δ(A,1),0),1) = δ(δ(B,0),1) = δ(C,1) = C In the Example DFA, set of final states F includes only A and B and upon extending the transition after reading 101 we are in state C, therefore 101 is not accepted, since state Cis not included as element of set F. 11 | P a g e 2.3 NONDETERMINISTIC FINITE AUTOMATA Definition: A nondeterministic finite automaton (NFA), M, is specified by a quintuple M= (Q, Σ, δ, s, F) where: Q is an alphabet of state symbols;  is an alphabet of input symbols; δ : Q x Σ → 2Q is a transition relation; s in Q is a start state; and F in Q is a set of final states Example: NFA M{Q, Σ, δ, q0, F} Q = {q0, q1, q2} Σ = {0, 1, 2} F = {q2} s(q0) = q0 0 1 2 q0 {q0, q1} {q0} {q2} q1 Ø {q2} Ø q2 {q0, q2} {q0, q1} {q0} 0,1 2 0 S 0 1 q0 q1 q2 1 0, 1, 2 2.4 THE EQUIVALENCE OF DFA’S AND NFA’S Theorem 2.1 Let L be a set accepted by an NFA then there exist a DFA that accept L. Let M = (Q, Σ, δ, s, F) be an NFA accepting L. Define a DFA, M’= (Q’, Σ, δ’, q0’, F’) where, 12 | P a g e  M’ are all the subsets of the set of states of M. Q’ = 2Q F’ is the set of all states in Q’ containing a final state of M δ’([q1, q2, …, qi], a) = [p1, p2, …, pj] [q1, q2, …, qi] is a single state of the DFA corresponding to a set of states of the NFA. Ex.{q0,q1} = [q0,q1] ([q0,q1] is considered as 1 state) 13 | P a g e 2.5 FINITE AUTOMATA WITH Є- MOVES We may naturally let є-CLOSURE(P), where P is a set of states, be q in p є -CLOSURE(g). Now we define 𝛿̂ as follows: 1) 𝛿̂ (𝑞, є) = є-CLOSURE(q). 2) For w in Σ* and a in Σ, 𝛿̂ (q, wa) = є-CLOSURE(P), where P = {p | for some r in , 𝛿̂ (q, w), p is in δ(r, a). It is convenient to extend 𝛿̂ and δ to sets of states by 3) δ(R, a) = q in R δ(q, a), and 4) 𝛿̂ (R, w) = q in R 𝛿̂ (q, w) for sets of states R. Not that in this 𝛿̂ (q, a) is not necessarily equal to δ(q, a), since 𝛿̂ (q, a) includes all states reachable from q by paths labeled a (including paths with arcs labeled є), while δ(q, a) includes only those states reachable from q by arcs labeled a. 𝛿̂ (q0, є) = є-closure(q0) = {q0, q1, q2} Thus 𝛿̂ (q0, 0) = є-closure (δ(𝛿̂ ( (q0, є), 0 )) = є-closure (δ({q0, q1, q2}, 0)) = є-closure (δ(q0, 0)  (q1, 0)   (q2, 0)) = є-closure ({q0}    ) = є-closure ({q0}) = {q0, q1, q2} 14 | P a g e  δ(q0, 01) = є-closure (δ(𝛿̂ ( (q0, 0), 1)) = є-closure (δ({q0, q1, q2}, 1)) = є-closure ({q1}) = {q1, q2} 2.6 EQUIVALENCE OF NFA’s WITH AND WITHOUT є-Moves Theorem 2.2 If L is accepted by an NFA with є-transitions, then L is accepted by an NFA without transitions. Proof Let M = (Q, Σ, δ, q0, F) be an NFA with є-transitions. Construct M’ = (Q, Σ, δ’, q0, F’) where F  {q0} if є-closure (q0) contains a state of F, F’ = F otherwise, and δ’(q, a) is 𝛿̂ (q, a) for q in Q and a in Σ. We wish to show by induction on |x | that δ’(q0, x) = 𝛿̂ (q0, x). However, this statement may not be true for x = є, since δ’(q0, є) = {q0}, while 𝛿̂ (q0, є) = є - CLOSURE(q0). We therefore begin our induction at 1. Basis | x | = 1. Then x is a symbol a, and δ’(q, a) = 𝛿̂ (q0, a) by definition of δ’. Induction |x| > 1. Let x = wa for symbol a in Σ. Then δ’(q0, wa) = δ’(δ’(q0, w), a). By the inductive hypothesis, δ’(q0, w) = 𝛿̂ (q0, w). Let 𝛿̂ (q0, w) = P. We must show that δ’(P, a) = 𝛿̂ (q0, wa). But δ’(P, a) =  δ’(q, a) = δ’(q0, a). q in P Then 𝛿̂ (q0, a) we have 𝛿̂ (q, a) = 𝛿̂ (q0, wa) q in P as P = by rule(2) in the definition of 𝛿̂. Thus δ’(q0, wa) = 𝛿̂ (q0, wa). 15 | P a g e Example: 1. NFA with є-Moves δ: 0 1 2 є q0 {q0} {} {} {q1} є-clo(q0) = {q0, q1, q2} q1 {} {q1} {} {q2} є-clo(q1) = {q1, q2} q2 {} {} {q2} {} є-clo(q2) = {q2} 0 1 2 S q0 є q1 є q2 Note: Given are NFA with є-moves to convert it to NFA without є-moves we need to create a new δ table by computing δ. (Example, input 0, 1, 2). δ(q0,0) = є-closure(δ(δ(q0, 0), 0)) = є-clo(δ({q0, q1, q2}, 0) = є-clo(δ(q0, 0)  (q1, 0)  (q2, 0)) = є-clo((q0)    ) = є-clo(q0) = {q0, q1, q2} δ(q0, 1) = є-clo(δ(δ(q0, є), 1)) = є-clo(δ({q0, q1, q2}, 1)) = є-clo(δ(q0, 1)   (q1, 1)  (q2, 1)) = є-clo(  {q1}  ) = є-clo({q1}) = {q1, q2} 16 | P a g e δ(q0, 2) = є-clo(δ(δ(q0, є), 2)) = є-clo(δ({q0, q1, q2}, 2)) = є-clo(δ(q0, 2)   (q1, 2)   (q0, 2)) = є-clo(    {q2}) = {q2} (q1, є) = є-clo(q1) = {q1, q2} δ(q2, є) = є-clo(q2) = {q2} δ(q1, 0) = є-clo(δ(δ(q1, є), 0)) = є-clo(δ({q1, q2}, 0)) = є-clo({(q1, 0)   (q2, 0)}) = є-clo(  ) = (q1, 1) = є-clo(δ(δ(q1, є), 1)) = є-clo(δ({q1, q2}, 1)) = є-clo(δ(q1, 1)   (q2, 1)) = є-clo({q1}  ) = є-clo({q1}) = {q1, q2} δ(q1, 2) = є-clo(δ(δ(q1, є), 2)) = є-clo(δ({q1, q2}, 2)) = є-clo(δ(q1, 2)   (q2, 2)) = є-clo(  {q2}) = є-clo({q2}) = {q2} δ(q2, 0) = є-clo(δ(δ(q2, є), 0)) = є-clo(δ({q2}, 0)) = є-clo(δ(q2, 0)) = є-clo() = 17 | P a g e δ(q2, 1) = є-clo(δ(δ(q2, є), 1)) = є-clo(δ({q2}, 1)) = є-clo(δ(q2, 1)) = є-clo() = (q2, 2) = є-clo(δ(δ(q2, є), 2)) = є-clo(δ({q2}, 2)) = є-clo(δ(q2, 2)) = є-clo({q2}) = {q2} F’ = ({q0}, {q2}) since є-clo(q0) = {q0, q1, q2} where F = {q2}  ’ : 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} q1  {q1, q2} {q2} q2   {q2} 0 1 2 S 0, 1 1, 2 q q q0 1 2 0, 1, 2 18 | P a g e 2.7 REGULAR EXPRESSION AND REGULAR LANGUAGE The languages accepted by finite automata are easily described by simple expressions called regular expressions. Let Σ be a finite set of symbols and let L, L1 and L2 be sets of strings from Σ*. The concatenation of L1 and L2, denoted L1L2, is the set {xy | x is in L1 and y is in L2}. That is, the strings in L1L2 are formed by choosing a string L1 and following it by a string in L2, in all possible combinations. Define L0 = {є} and Li = LLi – 1 for i ≥ 1. The Kleene closure of L, denoted L*, is the set ∞ i L* = L  i=0 and the positive closure of L, denoted L+ is the set ∞ i L+ = L  i=1 That is, L* denotes words constructed by concatenating any number of words from L. L+ is the same, but the case of zero words, whose "concatenation" is defined to be є, is excluded. 2.8 EQUIVALENCE OF FINITE AUTOMATA AND REGULAR EXPRESSIONS Nondeterministic finite automata Deterministic finite NFA’s automata with є-transitions Regular Expressions Theorem 2.3 Let r be a regular expression. Then there exists an NFA with є-transitions that accepts L(r). Proof We show by induction on the number of operators in the regular expression r that there is an NFA M with є-transitions, having one final state and no transitions out of this final state, such that L(M) = L(r). Basis (Zero operators) The expression r must be є, Ø, or a for some Σ in X. The NFA's in (a), (b), and (c) clearly satisfy the conditions. 19 | P a g e Start Start Start q q q (a) r = є (b) r = Ø (c) r =qa q 0 0 f 0 f Induction (One or more operators) Assume that the theorem is true for regular expressions with fewer than i operators, i > 1 Let r have i operators. There are 3 cases depending on the form of r. CASE 1 r = r 1 + r2 UNION q1 M1 f1 є є Start q0 f0 є q2 M2 f2 є CASE 2 r = r 1 r2 CONCATENATION є Start q1 M1 f1 q2 M2 f2 CASE 3 r = r1* є є є Start q0 q1 M1 f1 f0 є CLOSURE 20 | P a g e Example: Let us construct an NFA for the r.e. 01* + 1. By our precedence rules, this expressions is really (0(1*)) + 1, so it is of the form r1 + r2, where r1 = 01* and r2 = 1. The automaton for r2 is 1 Start q q 1 2 We may express r1 as r3 r4, where r3 = 0 and r4 = 1*. The automaton for r3 is 0 Start q q 3 4 In turn, r4 is r5*, where r5 is 1 An NFA r5 is 1 Start q q 5 6 Note that the need to keep states of different automata disjoint prohibits us from using the same NFA for r2 and r5, although they are the same expression. To construct a NFA for r4 = r5*, create states q7 and q8 playing the roles of q0 and f0. є є 1 є q q q q Start 7 5 6 8 є (a) 21 | P a g e  є 0 є є 1 є Start q q q q q q 4 7 5 6 8 3 є (b) 1 є q q є 1 Start є 2 q q є є 9 0 є є 1 є q q q q q q 8 3 4 7 5 є 6 Constructing an NFA from a regular expression (a) For r4 = 1* (b) For r1 = 01* (c) For r = 01* + 1 Theorem 2.4 If L is accepted by a DFA, then L is denoted by a regular expression. Proof Let L be the set accepted by the DFA M = ({q1, q2, … , qn}, Σ, δ, q1, F) 𝑘 Let R denote the set of all strings x such that δ(qi, x) = qj and if δ(qi, y) = qℓ, for any y that is a 𝑖𝑗 prefix of x, other than x or є, then ℓ < K. 𝑘 R is the set of all strings that take the FA from state qi to qj without going through any state 𝑖𝑗 numbered higher than k. Note that by "going through a state," we mean both entering and then leaving. Thus i or j may be greater than k. 22 | P a g e  𝑛 Since there is no state numbered greater than n, R𝑖𝑗 denotes all strings that take qi to qj. We can 𝑘 define R recursively: 𝑖𝑗 𝑘 𝑘−1 𝑘−1 𝑘−1 𝑘−1 R =R (R )* R ∪R , 𝑖𝑗 𝑖𝑘 𝑘𝑘 𝑘𝑗 𝑖𝑗 {a | δ(qi, a) = qj} if i ≠ j, 0 R = {a | δ(qi, a) = qj} ∪ {є} if i = j. 𝑖𝑗 𝑘 Informally, the definition of R above means that the inputs that cause M to go from qi to qj without 𝑖𝑗 passing through a state higher than qk are either 𝑘−1 1) in R (that is, they never pass through a state as high as qk); or 𝑖𝑗 𝑘−1 2) composed of a string in R (which takes M to qk for the first time) followed by zero or more 𝑖𝑘 𝑘−1 strings in R (which take M from qk back to qk without passing through qk or a higher- 𝑘𝑘 𝑘−1 numbered state) followed by a string in R (which takes M from state qk to qj). 𝑘𝑗 𝑘 We must show that for each i, j, and k there exists a regular expression r denoting the language 𝑖𝑗 𝑘 R. We proceed by induction on k. 𝑖𝑗 0 0 Basis (k = 0). R is a finite set of strings each of which is either є or a single symbol. Thus r 𝑖𝑗 𝑖𝑗 can be written as a1 + a2 + … + ap (or a1 + a2 + … + ap + є if i = j), where {a1, a2, …, ap} is the set of all symbols a such that δ(qi, a) = qj. If there are no such a’s then Ø (or є in the case i = j) serves 0 as r. 𝑖𝑗 𝑘 Induction The recursive formula for R given clearly involves only the regular expression 𝑖𝑗 operators: union, concatenation, and closure. By the induction hypothesis, for each ℓ and m there 𝑘−1 𝑘−1 𝑘−1 𝑘 exists a regular expression r such that L(r )=R. Thus for r we may select the ℓ𝑚 ℓ𝑚 ℓ𝑚 𝑖𝑗 regular expression 𝑘−1 𝑘−1 𝑘−1 𝑘−1 r (r )* (r )+ r , 𝑖𝑘 𝑘𝑘 𝑘𝑗 𝑖𝑗 which completes the induction. To finish the proof we have only to observe that 𝑛 L(M) =  R𝑖𝑗 q in F j 23 | P a g e  𝑛 since R𝑖𝑗 denotes the labels of all paths from qi to qj. Thus L(M) is denoted by the regular expression 𝑛 𝑛 𝑛 r1𝑗 + r1𝑗 + … + r1𝑗 , where F = { q𝑗1 , q𝑗2 , …, q𝑗𝑝 }. 1 2 𝑝 Example: Similarly, 2 1 1 1 1 r = r (r )* r + r = 0(є + 00)*(1 + 01) + 1 13 12 22 23 13 24 | P a g e Recognizing that (є + 00)* is equivalent to (00)* and that 1 + 01 is equivalent to (є + 0)1, we have 2 r = 0(00)*(є + 0)1 + 1. 13 Observe that (00)*(є + 0) is equivalent to 0*. Thus 0(00)*(є + 0)1 + 1 is equivalent to 00*1 + 1 and hence to 0*1. To complete the construction of the regular expression for M, which is 3 3 r + r , we write 12 13 3 2 2 2 2 r = r (r )* r + r 12 13 33 32 12 = 0*1(є + (0 + 1)0*1)*(0 + 1)(00)* + 0(00)* = 0*1((0 + 1)0*1 )*(0 + 1)(00)* + 0(00)* and 3 2 2 2 2 r = r (r )* r + r 13 13 33 33 13 = 0*1(є + (0 + 1)0*1)*(є + (0 + 1)0*1) + 0*1 = 0*1((0 + 1)0*1)*. Hence 3 3 r + r = 0*1((0 + 1)0*1)*(є + (0 + 1)(00)*) + 0(00)*. 12 13 25 | P a g e 2.9 FINITE AUTOMATA WITH OUTPUT One limitation of the finite automaton is that its output is limited to a binary to binary signl “accept”/”reject”. Models in which the output is chose from some other alphabet have been considered. Two distinct approaches: o The output may be associated with the state (Moore Machine) o The output may be associated with the transition (Mealy Machine) MOORE MACHINES Definition: Sixtuple machine, (Q, ∑, Δ, δ, λ, q0), where Q, ∑, δ, and q0 are as in the DFA. Δ is the output alphabet and λ is a mapping from Q to Δ giving the associated with each state. The output of M in response to input a1a2…an, n>0, is λ(q0) λ(q1)… λ(qn), where q0, q1…qn is the sequence of states. Note that any Moore machine gives output λ(q0) in response to input ε. The DFA may be viewed as a special case of a Moore machine where the output alphabet is {0, 1} and state q is "accepting" if and only if λ(q) = 1. MEALY MACHINES Definition: Sixtuple machine, (Q, ∑, Δ, δ, λ, q0), where all is as in the Moore machine, except that A maps Q x ∑ to Δ. That is, λ (q, a) gives the output associated with the transition from state q on input a. The output of M in response to input a1, a2,... an is λ (q0, a1) λ (q1, a2) … λ (qn-1, an) where q0, q1…qn is the sequence of states. Note that this sequence has length n rather than length n + 1 as for the Moore machine, and on input ε a Mealy machine gives output ε. 26 | P a g e  EQUIVALENCE OF MOORE AND MEALY MACHINES Let M be a Mealy or Moore machine. Define TM(w), for input string w, to be the output produced by M on input w. There can never be exact identity between the functions TM and TM. if M is a Mealy machine and M' a Moore machine, because | TM(w) | is one less than |TM(w) | for each w. However, we may neglect the response of a Moore machine to input ε and say that Mealy machine M and Moore machine M' are equivalent if for all inputs w, b TM(w), = TM(w), where b is the output of M' for its initial state. We may then prove the following theorems, equating the Mealy and Moore models. Theorem 2.6 If M1 = (Q, ∑, Δ, δ, λ, q0) is a Moore machine, then there is a Mealy machine M2 equivalent to M1. Proof Let M2 = (Q, ∑, Δ, δ, λ’, q0) is and define λ'(q, a) to be λ (δ (q, a)) for all states q and input symbols a. Then M1 and M2 enter the same sequence of states on the same input, and with each transition M2 emits the output that M1 associates with the state entered. Theorem 2.7 Let M2 = (Q, ∑, Δ, δ, λ, q0) be a Mealy machine. Then there is a Moore machine M2 equivalent to M1. Proof Let M2 = (Q x Δ, ∑, Δ, δ', λ’, [q0, b0]), where b0 is an arbitrarily selected member of Δ. That is, the states of M2 are pairs [q, b] consisting of a state of M1 and an output symbol. Define δ'([q, b], a) = [δ(q, a), λ(q, a)] and λ’([q, b]) = b. The second component of a state [q, b] of M2 is the output made by M1 on some transition into state q. Only the first components of M2’s states determine the moves made by M2. An easy induction on n shows that if M1 enters states q1, …, qn on input a1, a2 … an , and emits outputs b1, b2, … bn, then M2 enters states [q0, b0], [q1, b1], …, [qn, bn] and emits b0, b1, b2, … bn. Moore machine constructed from Mealy machine 27 | P a g e Exercises: 1. Which of the following 0001, 01001, 0000110 are accepted by the given dfa. Show your solution. δ a b ε ->1 ᴓ ᴓ {2,4} 2 ᴓ ᴓ {3} 3 ᴓ ᴓ {6} 4 {5} ᴓ ᴓ 5 ᴓ {6} {7} *6 ᴓ ᴓ ᴓ 7 ᴓ ᴓ ᴓ δ 0 1 ->Qo Q0 Q1 *Q1 Q0 Q2 Q2 Q2 Q1 2. A. Convert the given NFA to a DFA. Define the new machine DFA. δ 0 1 *->Qo {Q1} {Q2} Q1 {Q2} {Q0,Q2} Q2 ᴓ ᴓ B. Show if the following string is accepted by the NFA in No.2 and the resulting new machine after the conversion. String M M’ 1. 0010 2. 1001 C. Convert the given ε-NFA into its NFA equivalent. δ a b ε ->1 ᴓ ᴓ {2,4} 2 ᴓ ᴓ {3} 3 ᴓ ᴓ {6} 4 {5} ᴓ ᴓ 5 ᴓ {6} {7} *6 ᴓ ᴓ ᴓ 7 ᴓ ᴓ ᴓ 1. Define the new machine. 28 | P a g e 2. Show your solution for the computations of δ’. 3. Define all the ε-closure for all Q. D. Convert the given r.e. into its ε-NFA equivalent. r.e. 1*00+(00)+ 1. How many machines will be constructed from the derived set of r.e.? 2. How many states will be used to construct the final machine? 3. Show your solutions for each r.e. E. Convert the given DFA to its equivalent r.e. δ 0 1 A B A B B A 1. Complete the table for computation 2. Show your solution. 3. What is L(r)? 29 | P a g e 3.0 Properties of Regular Sets Overview: This section will explain the closure properties of languages under different operations, the lemmas to be used to prove if the language is regular. Objectives: At the end of the lesson the student will be able to: 1. Discuss closure of regular language under operations 2. Construct models for regular language, also models as a result of operation/s on that langauges 3. Explain the closure properties of regular sets 4. Explain how proving can be done to prove a language is not regular 5. Explain the importance of minimization of DFA 6. Construct minimized DFA 3.1 THE PUMPING LEMMA FOR REGULAR SETS Definition: A powerful tool for proving certain languages to be nonregular. It is also useful in the development of algorithms to answer certain questions concerning finite automata, such as whether the language accepted by a given FA is finite or infinite. If a language is regular, it is accepted by a DFA M = (Q, ∑, δ, q0, F) with some particular number of states, say n. Consider an input of n or more symbols a1 a2 … am, m ≥ n, and for i = 1, 2,..., m let δ (q0, a1 a2 … ai) = qi. It is not possible for each of the n + 1 states q0, q1, … qn to be distinct, since there are only n different states. Thus there are two integers j and k, 0 ≤ j < k ≤ n, such that q j = qk. Since j < k, the string aj+1... ak is of length at least 1, and since k ≤ n, its length is no more than n. aj+1 … ak a1 … aj ak+1 … am q0 q 1 = qk qm Path in transition diagram of DFA M If qm is in F, that is, a1 a2 … am is in L(M), then a1 a2 … aj ak+1 ak+2 … am is also in L(M), since there is a path from q0 to qm that goes through qj but not around the loop labeled aj+1 … ak. 30 | P a g e Pumping lemma. Let L be a regular set. Then there exists a constant n such that if z is any wird in L and z  n, we may write z = uvw in such a way that |uv| n, |v|  1, such that and for all i  0, uviw is in L. Note that the pumping lemma states that if a regular set contains a long string z, then it contains an infinite set of strings of the form uviw. The lemma does not state that every sufficiently long string in a regular set is of the form uviw for some large i. In fact, (0 + 1)* contains arbitrarily long strings in which no substring appears three times consecutively. (The proof is left as an exercise.) 3.2 CLOSURE PROPERTIES OF REGULAR SETS Theorem 3.1 The regular sets are closed under union, concatenation, and Kleene closure. Proof Immediate from the definition of regular expressions. Boolean operations Theorem 3.2 The class of regular sets is closed under complementation. That is, if L is a regular set and L ⊆ ∑*, then ∑* - L is a regular set. Proof: Let L be L(M) for DFA M = (Q, ∑, δ, q0, F) and let L ⊆ ∑*. First, we may assume ∑1 = ∑, for if there are symbols in ∑1 not in ∑, we may delete all transitions of M on symbols not in ∑. If there are symbols in ∑ not in ∑1 then none of these symbols appear in words of L. We may therefore introduce a "dead state" d into M with δ (d, a) = d for all a in ∑ and δ(q a) = d for all q in Q and a in ∑ - ∑1 Now, to accept ∑* - L, complement the final states of M. That is, let M' = (Q, ∑, δ, q0, F). Then M' accepts a word w if and only if δ (q0, w) is in Q - F, that is, w is in ∑* - L. Note that it is essential to the proof that M is deterministic and without £ moves. 31 | P a g e Theorem 3.3 The regular sets are closed under intersection. _______ ̅̅̅1 ∪ 𝐿 Proof Ll ∩ L2 = 𝐿 ̅̅̅2 where the overbar denotes complementation with respect to an alphabet including the alphabets of Ll and L2. Closure under intersection then follows from closure under union and complementation. It is worth noting that a direct construction of a DFA for the intersection of two regular sets exists. The construction involves taking the Cartesian product of states, and we sketch the construction as follows. Let M1 = (Q1, ∑, δ1, q1, F1) and M2 = (Q2, ∑, δ2, q2, F2) be two deterministic finite automata. Let M = (Q1 x Q2, ∑, δ, [q1, q2], F1 x F2), where for all p1 in Q1, p2 in Q2, and a in ∑, δ([p1, p2], a) = [δ1 (p1, a), δ2(p2, a)] It is easily shown that L(M) = L(M1) ∩ L(M2). Substitutions and homomorphisms The class of regular sets has the interesting property that it is closed under substitution in the following sense. For each symbol a in the alphabet of some regular set R, let Ra be a particular regular set. Suppose that we replace each word a1 a2 … an in R by the set of words of the form w1 w2 … wm where wi is an arbitrary word in Rai. Then the result is always a regular set. More formally, a substitution f is a mapping of an alphabet ∑ onto subsets of Δ*, for some alphabet Δ. Thus f associates a language with each symbol of ∑. The mapping f is extended to strings as follows: 1) f (є) = є; 2) f (xa) = f (x) f (a). The mapping f is extended to languages by defining f (L) =  f (x) x in L Theorem 3.4 The class of regular sets is closed under substitution. Proof Let R ⊆ ∑* be a regular set and for each a in ∑ let Ra ⊆ Δ * be a regular set. Let f: ∑ → Δ * be the substitution defined by f(a) = Ra. Select regular expressions denoting R and each Ra. Replace each occurrence of the symbol a in the regular expression for R by the regular expression for Ra. To prove that the resulting regular expression denotes f(R) observe that the substitution of a union, product, or closure is the union, product, or closure of the substitution. 32 | P a g e  A type of substitution that is of special interest is the homomorphism. A homomorphism h is a substitution such that h(a) contains a single string for each a. We generally take h(a) to be the string itself, rather than the set containing that string. It is useful to define the inverse homomorphic image of a language L to be h-l(L) = {x | h(x) is in L}. We also use, for string w; h-l(w) = {x | h(x) is in w}. A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet. Example: Let h(0) = aa h(1) = aba Then h(010) = aaabaaa If Ll is (01)*, then (Ll) is (aaaba)*. Theorem 3.5 The class of regular sets is closed under homomorphisms and inverse homomorphisms. Proof Closure under homomorphisms follows immediately from closure under substitution , since every homomorphism is a substitution, in which h(a) has one member. To show closure under inverse homomorphism, let M = (Q, ∑, δ, q0, F) be a DFA accepting L, and let h be a homomorphism from Δ to ∑*. We construct a DFA M' that accepts h-1(L) by reading symbol a in Δ and simulating M on h(a). Formally, let M’ = (Q, ∑, δ’, q0, F) and define δ’(q, a), for q in Q and a in Δ to be δ(q, h(a)). It is easy to show by induction on |x| that δ’(q0, x) = δ(q0, h(x)). Therefore M' accepts x if and only if M accepts h(x). That is, L(M') = h-l(L(M)). Example Prove that {anban | n ≥ 1} is not regular. Let h1 and h2 be the homomorphisms h1 (a) = a, h2 (a) = 0, h1 (b) = ba, h2 (b) = l, h1 (c) = a, h2 (c) = 1. Then h1-1 ({anban | n ≥ 1}) ∩ a*bc* = { anbcn-1 | n ≥ 1} If {anban | n ≥ 1} were regular, then since homomorphisms, inverse homomorphisms, and intersection with a regular set all preserve the property of being regular, it would follow that {0n1n | n ≥ 1} is regular, a contradiction. 33 | P a g e THE MYHILL-NERODE THEOREM AND MINIMIZATION OF FINITE AUTOMATA Theorem 3.9 (The Myhill-Nerode theorem). The following three statements are equivalent: 1) The set L is accepted by some finite automaton. 2) L is the union of some of the equivalence classes of a right invariant equivalence relation of finite index. 3) Let equivalence relation RL be defined by: xRLy if and only if for all z in ∑*, xz is in L exactly when yz is in L Then RL is of finite index. Proof (1) → (2) Assume that L is accepted by some DFA M = (Q, ∑, δ, q0, F). Let RM be the equivalence relation xRMy if and only if δ(q0, y). RM is right invariant since, for any z, if δ(q0, x) = δ(q0, y), then δ(q0, xz) = δ(q0, yz). The index of RM is finite, since the index is at most the number of states in Q. Furthermore, L is the union of those equivalence classes that include a string x such that δ(q0, x) is in F, that is, the equivalence classes corresponding to final states. (2) → (3) We show that any equivalence relation E satisfying (2) is a refinement of RL; every equivalence class of £ is entirely contained in some equivalence class of RL. Thus the index of RL cannot be greater than the index of E and so is finite. Assume that xEy. Then since E is right invariant, for each z in ∑*, xzEyz, and thus yz is in L if and only if xz is in L. Thus xRLy, and hence the equivalence class of x in £ is contained in the equivalence class of x in RL. We conclude that each equivalence class of E is contained within some equivalence class of RL. (3) → (1) We must first show that RL is right invariant. Suppose xRLy and let w be in ∑*. We must prove that xwRLyw; that is, for any z, xwz is in L exactly when ywz is in L. But since xRLy, we know by definition of RL that for any v, xv is in L exactly when yv is in L. Let v = wz to prove that RL is right invariant. Now let Q' be the finite set of equivalence classes of RL and [x] the element of Q' containing x. Define δ’([x], a) = [xa]. The definition is consistent, since RL is right invariant. Had we chosen y instead of x from the equivalence class [x], we would have obtained δ’([x], a) = [ya]. But xRLy, so xz is in L exactly when yz is in L. In particular, if z = az', xaz' is in L exactly when yaz' is in L, so xaRLya, and [xa] = [ya]. Let q’0 = [є] and let F’ = {[x] | x is in L}. The finite automaton M’ = (Q, ∑, δ’, q’0, F’) accepts L, since δ’(q’0, x) = [x], and thus x is in L(M’) if an only if [x] is in F’. Example: Let L be the language 0*10*. L is accepted by the DFA M below. 34 | P a g e  Consider the relation RM defined by M. DFA M accepting L As all states are reachable from the start state, RM has six equivalence classes, which are Ca = (00)*, Cd = (00)*01, Cb = (00)*0, Ce = 0*100*, Cc = (00)*1, Cf = 0*10*1(0 + 1)* L is the union of three of these classes, Cc, Cd, Ce. The relation RL for has xRLy iff either i) x and y each have no 1’s, ii) x and y each have one 1, or iii) x and y each have more than one 1. For example, if x = 010 and y = 1000, then xz is in L if and only if z is in 0*. But yz is in L under exactly the same conditions. As another example, if x = 01 and y = 00, then we might choose z = 0 to show that xRLy is false. That is, xz = 010 is in L, but yz = 000 is not. We may denote the three equivalence classes of RL by C1 = 0*, C2 = 0*10*, and C3 = 0*10*1(0 + 1)*. L is the language consisting of only one of these classes, C2. From RL we may construct a DFA as follows. 35 | P a g e  Pick representatives for C1, C2, and C3, say є, 1, and 11. Then let M' be the DFA shown. For example, δ '(, 0) = , since w is any string in (note is C1), say 0i10j, then w0 is 0i10j+1, which is also in C1 = 0*10*. 0 0 0,1 Start 1 [ 1 [1 | 1 1] ε ] 3.3 MINIMIZATION OF DFA | A minimization algorithm Let ≡ be the equivalence relation on the states of M such that p ≡ q if and only if for each input string x, δ(p, x) is an accepting state if and only if δ(q, x) is an accepting state. Observe that there is an isomorphism between those equivalence classes of ≡ that contain a state reachable from q0 by some input string and the states of the minimum state FA M'. Terminologies to consider: o If p = q, we say p is equivalent to q. o We say that p is distinguishable from q if there exists an x such that δ(p, x) is in F and δ(q, x) is not, or vice versa. Theorem 3.10 The minimum state automaton accepting a set L is unique up to an isomorphism (i.e., a renaming of the states) and is given by M' in the proof of Theorem 3. Proof In the proof of Theorem 3.9 we saw that any DFA M = (Q, ∑, δ, q0, F) accepting L defines an equivalence relation that is a refinement of RL. Thus the number of states of M is greater than or equal to the number of states of M' of Theorem 3.9. If equality holds, then each of the states of M can be identified with one of the states of M'. That is, let q be a state of M. There must be some x in ∑*, such that δ(q0, x) = q, otherwise q could be removed from Q, and a smaller automaton found. Identify q with the state δ’(q’0, x), of M’. This identification will be consistent. If δ(q0, x) = δ(q0, y) = q, then, by the proof of Theorem 3.9, x and y are in the same equivalence class of RL. Thus δ’(q’0, x) = δ’(q’0, y). 36 | P a g e Example: Given: An X will be placed in the table each time we discover a pair of states that cannot be equivalent. 37 | P a g e  Initially an X is placed in each entry corresponding to one final state and one nonfinal state. In our example, we will place an X in the entries (a, c), (b, c), (c, d), (c, e), (c, f), (c, g) and (c, h). Next for each pair of states p and q that are not already known to be distinguishable we consider the pair of states r = δ(p, a) and s = δ(q, a) for each input symbol a. If states r and s have been shown to be distinguishable by some string x, then p and q are distinguishable by string ax. Thus if the entry (r, s) in the table has an X, an X is also placed at the entry (p, q). If the entry (r, s) does not yet have an X, then the pair (p, q) is placed on a list associated with the (r, s) entry. At some future time, if the (r, s) entry receives an X, then each pair on the list associated with the (r, s) entry also receives an X. Algorithm for marking pairs of inequivalent states begin 1) for p in F and q in Q - F do mark (p, q); 2) for each pair of distinct states (p, q) in F x F or (Q - F) x (Q - F) do 3) if for some input symbol a, (δ(p, a), δ(q, a)) is marked then begin 4) mark (p, q); 5) recursively mark all unmarked pairs on the list for (p, q) and on the lists of other pairs that are marked at this step. end else 6) for all input symbols a do 7) put (p, q) on the list for (δ(p, a), δ(q, a)) unless 8) δ (p, a) = δ(q, a) end Theorem 3.11 The DFA constructed by the algorithm, with inaccessible states removed, is the minimum state DFA for its language. Proof Let M = (Q, ∑, δ, q0, F) be the DFA to which the algorithm is applied and M' = (Q’, ∑, δ’, [q0], F’) be the DFA constructed. That is, Q = {[q] | q is accessible from q0}, F' = {[q] | q is in F} and 38 | P a g e  δ’([q] a) = [δ’(q,a)] δ’is consistently defined, since if q ≡ p, then δ(q, a) ≡ δ(p, a). That is, if δ (q, a) is distinguished from δ(p, a) by x, then ax distinguishes q from p. It is also easy to show that δ’([q0] w) = [δ([q0] w)] by induction on |w|. Thus L(M') = L(M). We must show that M' has no more states than RL has equivalence classes, where L = L(M). Suppose it did; then there are two accessible states q and p in Q such that [q] ≠ [p], yet there are x and y such that δ(q0, x) = q, δ(q0, y) = p, and xRLy. We claim that p ≡ q, for if not, then some w in L* distinguishes p from q. But then xwRLyw is false, for we may let z = є and observe that exactly one of xwz and ywz is in L. But since RL is right invariant, xwRLyw is true. Hence q and p do not exist, and M' has no more states than the index of RL. Thus M' is the minimum state DFA for L. Exercises: 1. Given two DFAs J and K, modify the cartesian product construction for intersection to write a procedure that will construct a DFA whose language is a. L(J) U L(K), the union operation, and b. L(J) – L(K), the set difference operation. 2. Show that {0i1j|gcd(I,j) = 1} is not regular. 3. Find the minimum-state finite automaton equivalent to the transition table δ 0 1 ->A B A B A C C D B *D D A E D F F G E G F G H G D 39 | P a g e 4.0 CONTEXT FREE GRAMMAR Overview Objectives: 1. Explain the difference of CFG and BNF 2. Apply the use of CFG by creating grammar rules 3. Derive sentences using the grammar rules 4. Explain how CFG can be simplified 5. Explain the difference of the formats CNF and GNF 6. Construct the equivalent grammar rules from CFG to CNF to GNF Context Free Grammars (CFG) A context-free grammar is a finite set of variables each of which represents a language. The languages represented by the variables are described recursively in terms of each other and primitive symbols called terminals. The rules relating the variables are called productions. Example: A CFG for palindromes 1. P → є 2. P → 0 3. P → 1 4. P → 0P0 5. P → 1P1 Definition of Context Free Grammars There are four components in a grammatical description of a language: 1. There is a finite set of symbols that form the strings of the language being defined. This set was {0, 1} in the palindrome example we just saw. We call this alphabet the terminals, or terminal symbols. 2. There is a finite set of variable, also called sometimes non-terminals or syntactic categories. Each variable represents a language; i.e., a set of strings. In our example above, there was only one variable P, which we used to represent the class of palindromes over alphabet {0, 1}. 3. One of the variables represents the language being defined; it is called the start symbol. Other variables represent auxiliary classes of strings that are used to help define the language of the start symbol. In our example, P, the only variable, is the start symbol. 40 | P a g e  4. There is a finite set of productions or rules that represent the recursive definition of a language. Each production consists of: a. A variable that is being (partially) defined by the production. This variable is often called the head of the production. b. The production symbol →. c. A string of zero or more terminals and variables. This string, called the body of the production, represents one way to form string in the language of the variable of the head. In so doing, we leave terminals unchanged and substitute for each variable of the body any string that is known to be in the language of that variable. The four components just described form a context-free grammar. CONVENTIONS: 1. A, B, C, D, E, and S denote variables. 2. a, b, c, d, e, digits, boldface strings denote terminals 3. X, Y, Z denote either terminals or variables 4. u, v, w, x, y, and z denote strings of terminals 5. α, β, γ denote strings of variables and terminals. We shall represent a CFG G by its four components, that is G = (V, T, P, S) where: V – set of variables T – terminals P – set of productions S – start symbol Example: The grammar Gpal = ({P}, {0,1}, A, P} Derivations Using a Grammar Recursive Inference – we take strings known to be in the language of each of the variables of the body, concatenate them, in the proper order, with any terminals appearing in the body, and infer that the resulting string is in the language of the variable in the head. (body-head) Derivation – we expand the start symbol using one of its productions. We further expand the resulting string by replacing one of the variables by the body of one of its productions, and so 41 | P a g e on, until we derive a string consisting entirely of terminals. The language of the grammar is all strings of terminals that we can obtain in this way. (head-body) The set of productions defining arithmetic expressions: → + → * → → id APPLICATION: → * → () * → () * id → ( + ) * id → ( + id) * id → (id + id) * id Theorem 4.1 Let G = (V, T, P, S) be a context-free grammar. S *⇒ α if and only if there is a derivation tree in given FG with yield α. DEFINITION: If w is in L(G) for CFG G, then w has at least one parse tree. And corresponding to a particular parse tree, w has a unique leftmost and a unique rightmost derivation. W may have several rightmost of leftmost derivations since there may be more than one parse tree for w. From each derivation tree, only one leftmost and one rightmost derivation may be obtained. A CFG G such that some word has two parse trees is said to be ambiguous, i.e., some word has more than one leftmost or more than one rightmost derivation. A CFG G such that some word has two parse trees is said to be ambiguous, i.e., some word has more than one leftmost or more than one rightmost derivation. LEFTMOST AND RIGHTMOST DERIVATIONS; AMBIGUITY If at each step in derivation a production is applied to the leftmost variable, then the derivation is said to be leftmost. 42 | P a g e Similarly a derivation in which the rightmost variable is replaced at each step is said to be rightmost. Example: LEFTMOST DERIVATION of string aabbaa S → aAS → aSbAS → aabAS → aabbaS → aabbaa Corresponding RIGHTMOST DERIVATION S → aAS → aAa → aSbAa → aSbbaa → aabbaa A context-free grammar G such that some word has two parse trees is said to be ambiguous. 4.1 DERIVATION TREES Derivation trees or parse trees superimpose a structure on the words of a language that is useful in applications such as the compilation of programming languages. The vertices of a derivation tree are labeled with terminal or variable symbols of the grammar or possibly with є. If an interior vertex n is labeled A, and the sons of n are labeled X1, X2,..., Xk from the left, then A→ X1, X2,..., Xk must be a production. Example: 43 | P a g e Example: Consider the grammar G = ({S, A}, {a, b}, P, S), where P consists of S → aAS | a A → SbA | SS | ba 44 | P a g e  SIMPLIFICATION OF CONTEXT-FREE GRAMMARS Useless Symbols Lemma 4.1 Given a CFG G = (V, T, P, S), with L(G) ≠ 0 we can effectively find an equivalent CFG G’ = (V’, T, P’, S) such that for each A in V’ there is some w in T* for which A *⇒ w. Lemma 4.2 Given a CFG G = (V, T, P, S) we can effectively find an equivalent CFG G’ – (V’, T’, P’, S) such that for each X in V’ ∪ T’ there exist α and β in (V’ ∪ T’)* for which S *⇒ αXβ. Theorem 4.2 Every non-empty CFL is generated by a CFG with no useless symbols. Example: Consider the grammar S → AB | a A→a Applying Lemma 4.1, we find that no terminal string is derivable from B. We therefore eliminate B and S → AB. S→a A→a Applying Lemma 4.2 to the grammar, we find that only S and a appear in sentential forms. Thus ({5}, {a}, {S → a}, S) is an equivalent grammar with no useless symbols. S→a є-Productions Theorem 4.3 If L = L(G) for some CFG G = (V, T, P, S), then L – {є} is L(G’) for a CFG G’ with no useless symbols or є-productions. Theorem 4.4 Every CFL without є is defined by a grammar with no useless symbols, є-productions, or unit productions. Example for a grammar G with e - productions is S → ABA A → aA | є B → bB | є The procedure to find out an equivalent G without є -productions 1. Find nullable variables 45 | P a g e  2. Add productions with nullable variables removed. 3. Remove є -productions and duplicates Step 1: Find set of nullable variables Nullable variables: Variables that can be replaced by null (є). If A * є then A is a nullable variable. In the grammar with productions S → ABA, A → aA | є, B → bB | є, A is nullable because of the production A → є. B is nullable because of the production B → є. S is nullable because both A and B are nullable. Step 2: Add productions with nullable variables removed For each production of the form A → w, create all possible productions of the form A → w’, where w’ is obtained from w by removing one or more occurrences of nullable variables. S → ABA A → aA | є B → bB | є After removing nullable variables we get the productions S → ABA | BA | AA | AB | A | B | є A → aA | є | a B → bB | є | b Step 3: Remove є -productions and duplicates The desired grammar consists of the original productions together with the productions constructed in step 2, minus any productions of the form A → є. S → ABA | BA | AA | AB | A | B A → aA | a B → bB | b 46 | P a g e 4.2 CHOMSKY NORMAL FORM (CNF) Theorem 4.5 Any context-free language without є is generated by a grammar in which all productions are of the form A → BC or A → a. Here, A, B, and C, are variables and a is a terminal. Proof Let G be a context-free grammar generating a language not containing e. By Theorem 4.4, we can find an equivalent grammar, G1 = (K, T, P, S), such that P contains no unit productions or є-productions. Thus, if a production has a single symbol on the right, that symbol is a terminal, and the production is already in an acceptable form. Example: S → bA | aB A → bAA | aS | a B → aBB | bS | b Replace S → bA by S → CbA where Cb → b A → aS by A → CaS where Ca → a A → bAA by A → CbAA S → aB by S → CaB B → bS by B → CbS B → aBB by B → CaBB Current grammar: S → CbA | CaB A → CbAA | CaS | a B → CaBB | CbS | b Replace A → CbAA by A → CbD1 where D1 → AA B → CaBB by B → CaD2 where D2→ BB The final grammar in CNF S → CbA | CaB A → CbD1 | CaS | a B → CaD2 | CbS | b Cb → b 47 | P a g e  Ca → a D1 → AA D2→ BB 4.3 GREIBACH NORMAL FORM (GNF) A normal-form theorem that uses productions whose right-hand sides each start with a terminal symbol perhaps followed by some variables Lemma 4.3 Define an A-production to be a production with variable A on the left. Let G = (V, T, P, S) be a CFG. Let A → α1Bα2 be a production in P and B → β1 | β2| … βr be the set of all B-productions. Let G1 = (V, T, P1, S) be obtained from G by deleting the production A → α1Bα2 from P and adding productions A → α1 β1 α2 | … | α1 βr α2. Then L(G) = L(G1). Proof Obviously L(G1) ⊆ L(G) since A → α1Bα2 is used in a derivation of G1, then A ⇒G α1Bα2 ⇒G α1βiα2 can be used in G. To show that L(G1) ⊆ L(G), one simply notes that A → α1Bα2 is the only production in G not in G1. Whenever A → α1Bα2 is used in a derivation by G, the variable B must be rewritten at some later step using a production of the form B → βi. These two steps can be replaced by the single step A ⇒G α1βiα2. Lemma 4.4 Let G = (V, T, P, S) be a CFG. Let A → A α1 | A α2 | … | Aαr be the set of A-productions for which A is the leftmost symbol of the right-hand side. Let A → β1 | β2| … βs be the remaining A-productions. Let G1 = (V ∪ {B}, T, P1, S) be the CFG formed by adding the variable B to V and replacing all the productions by the productions: 1. A → βi A → β1B 1 ≤ i ≤ s, 2. B → αi B → αiB 1 ≤ i ≤ r. Then L(G1) = L(G). 48 | P a g e Theorem 4.6 Every context-free language L without є can be generated by a grammar for which every production is of is of the form A→ aα act, where A is a variable, a is a terminal , and α is a (possibly empty) string of variables. Proof Let G = (V9 T, P, S) be a Chomsky normal form grammar generating the CFL L Assume that V = {A1, A2, …, Am}. The first step in the construction is to modify the productions so that if Ai → Ajγ is a production, then j > i. Starting with A1 and proceeding to Am we do this as follows. We assume that the productions have been modified so that for 1 ≤ I < k, Ai → Ajγ is a production if and only if j > i. We now modify the Ak-productions. If Ak → Ajγ is a production with j < k, we generate a new set of productions by substituting for A j the right-hand side of each Aj-production according to Lemma 4.3. By repeating the process k - 1 times at most, we obtain productions of the form Ak → Aℓγ, ℓ ≥ k. The productions with ℓ = k are then replaced according to Lemma 4.4, introducing a new variable Bk. Greibach Normal-Form algorithm begin 1) for k:i= 1 to m do begin 2) for j:= 1 to k - 1 do 3) for each production of the form Ak → Aj α do begin 4) for all productions Aj → β do 5) add production Ak → βα; 6) remove production Ak → Ajα end; 7) for each production of the form Ak → Ak α do begin 8) add productions Bk → α and Bk → αBk; 9) remove production Ak → Akα end; 10) for each production Ak → β, where β does not begin with Ak do add production Ak → βBk end end Example: Let us convert the grammar Greibach normal form the grammar G= ({A1, A2, A3}, {a, b}, P, A1), where P consists of the following: A1 → A2A3 A2 → A3A1 | b A3→ A1A2 | a 49 | P a g e Step 1 Since the right-hand side of the productions for A1 and A2 start with terminals or higher- numbered variables, we begin with the production A3 -> A1 A2 and substitute the string A2A3for A1. Note that A1 → A2A3is the only production with A1 on the left. The resulting set of productions is: A1 → A2A3 A2 → A3A1 | b A3→ A2A3A2 | a (1) Since the right side of the production A3→ A2A3A2 begins with a lower numbered variable , we substitute for the first occurrence of A2 both A3A1 and b. Thus A3→ A2A3A2 is replaced by A3→ A3A1A3A2 and A3→ bA3A2 The new set is A1 → A2A3 A2 → A3A1 | b A3→ A3A1A3A2 | bA3A2 | a We now apply Lemma 4.4 to the productions A3→ A3A1A3A2 | bA3A2 | a Symbol B3 is introduced, and the production A3→ A3A1A3A2 is replaced by A3→ aB3 | bA3A2 B3 | bA3A2 | a B3 → A1A3A2 | A1A3A2 B3.The resulting set is A1 → A2A3 A2 → A3A1 | b A3→ aB3 | bA3A2 B3 | bA3A2 | a B3 → A1A3A2 | A1A3A2 B3 (2) Now all the productions with A3 on the left have right-hand sides that start with terminals. These are used to replace A3 in the production A2 → A3A1. 50 | P a g e Then the productions with A2 on the left are used to replace A2 in the production A1 → A2A3. The result is the following: B3 → A1A3A2 | A1A3A2 B3 A3→ aB3 | bA3A2 B3 | bA3A2 | a A2 → aB3 A1 | bA3A2 B3 A1 | bA3A2 A1 | aA1 | b A1 → aB3 A1 A3 | bA3A2 B3 A3 | bA3A2 A1 A3 | aA1A3 | b A3 Step 3 The two B3-productions are converted to proper form, resulting in 10 more productions. That is, the production B3 → A1A3A2 and B3 → A1A3A2 B3 are altered by substituting the right side of each of the five productions with A1 on the left for the first occurrences of A1. The final set of productions: A1 → aB3 A1 A3 B3 → aB3 A1 A3A3A2 A1 → bA3A2 B3 A3 B3 → bA3A2 B3 A3A3A2 A1 → bA3A2 A1 A3 B3 → bA3A2 A1 A3 A3A2 A1 → aA1A3 B3 → aA1A3A3A2 A1 → bA3 B3 → bA3A3A2 A2 → aB3 A1 B3 → aB3 A1 A3A3A2 B3 A2 → bA3A2 B3 A1 B3 → bA3A2 B3 A3A3A2 B3 A2 → bA3A2 A1 B3 → bA3A2 A1 A3 A3A2 B3 A2 → aA1 B3 → aA1A3A3A2 B3 A2 → b B3 → bA3A3A2 B3 A3→ aB3 A3→ bA3A2 B3 A3→ bA3A2 A3→ a 51 | P a g e 4.4 THE EXISTENCE OF INHERENT AMBIGUOUS CFL Lemma 4.5 Let (Ni, Mi), 1 ≤ i ≤ r, be pairs of sets of integers. Let Si = {(n, m) | n in Ni, m in Mi} and let S = S1 ∪ S2 … ∪ Sr. If each pair of integers (n, m) is in S for all n and m, where n ≠ m, then (n, n) is in S for all but some finite set of n. Proof Assume that for all n and m, where n ≠ m, each (n, m) in is S, and that there are infinitely many n such that (n, n) is not in S. Let J be the set of all n such that (h, m) is not in S. We construct a sequence of sets Jr, Jr-1, …, J1 such that J ⊇ Jr ⊇ Jr-1 ⊇ … ⊇ J1. Each Ji will be infinite, and for each n and m in Ji, (n, m) is not in Si ∪ Si+1 ∪ … ∪ Sr. For n in J, either n is not in Nr or n is not in Mr; otherwise (n, n) would be in Sr and hence in S. Thus there is an infinite subset of J, call it Jr, such that either for all n in Jr, n is not in Nr, or for all n in Jr, n is not in Mr. Now for n and m in Jr, (n, m) is not in Sr. Assume that Jr, Jr-1, …, Ji + 1 have been constructed, where i ≤ r – 1. Then Ji is constructed as follows. For each n in Ji + 1, either n is not in Ni or not in Mi; otherwise (n, n) would be in Si and hence in S, a contradiction since Ji + 1 ⊆ J. Thus, either an infinite subset of Ji + 1 is not in Ni or an infinite subset of Ji + 1 is not in Mi. In either case, let the infinite subset be Ji. Now for all n and m in Ji, (n, m) is not in Si and hence not in Si ∪ Si+1 ∪ … ∪ Sr. Since contains an infinite number of elements, there exist n and m in J1, n ≠ m. Now (n, m) is not in Si ∪ Si+1 ∪ … ∪ Sr = S, contradicting the assumption that all (n, m), where n ≠ m, are in S. Thus (n, n) is in S for all but some finite set of n. Lemma 4.6 Let G be an unambiguous CFG. Then we can effectively construct an unambiguous CFG G’ equivalent to G, such that G’ has no useless symbols or productions, and for every variable A other than possibly the start symbol of G’, we have the derivation A *⇒G’ x1 Ax2, where x1 abd x2 are not both є. Proof The construction of Lemmas 4.1 and 4.2, removing useless symbols and productions, cannot convert an unambiguous grammar into an ambiguous ojj , since the set of derivation trees for words does not change. The construction of Theorem 4.4, removing unit productions, cannot introduce ambiguities. This is because if we introduce production A → α there must be a unique B such that A ⇒* B and B → α is a production, else the original grammar was not unambiguous. Similarly, the construction of Theorem 4.3, removing є-productions, does not introduce ambiguity. Let us therefore assume that G has no useless symbols or productions, no є-productions, and no unit productions. Suppose that for no x1 and x2 not both є does A *⇒ x1 Ax2. Then replace each occurrence of A on the right side of any production by all the right sides of A-productions. 52 | P a g e As there are no unit productions, є-productions or useless symbols, there cannot be a production A → α1Aα2. else there is a derivation A *⇒ x1 Ax2, with x1 and x2 not both є. The above change does not modify the generated language, by Lemma 4.3. Each new production comes from a unique sequence of old productions, else G was ambiguous. Thus the resulting grammar is unambiguous. We see that A is now useless and may be eliminated. After removing variables violating the condition of the lemma in this manner, the new grammar is equivalent to the old, is still unambiguous, and satisfies the lemma. Theorem 4.7 The CFL, L = {anbncmdm | n ≥ 1, m ≥ 1} ∪ {anbmcmdn | n ≥ 1, m ≥ 1}, is inherently ambiguous. Proof Assume that there is an unambiguous grammar generating L. By Lemma 4.6 we can construct an unambiguous grammar G = (V, T, P, S) generating L with no useless symbols, and for each A in V – {S}, A*⇒ x1Ax2 for some x1 and x2 in T*, not both є. We note that the grammar G has the following properties: 1) If A *⇒ x1Ax2 then x1 and x2 each consist of only one type of symbol (a, b, c, or d); otherwise S *⇒ w1 Aw3 *⇒ w1x1x1w2x2x2w3, for some w1, w2, and w3. This last terminal string is not in L, 2) If A*⇒ x1Ax2 then x1 and x2 consist of different symbols. Otherwise, in a derivation involving A, we could increase the number of one type of symbol in a sentence of L without increasing the number of any other type of symbols, thereby generating a sentence not in L. 3) If A*⇒ x1Ax2 then |x1| and |x2|. Otherwise we could find words in L having more of one symbol than any other. 4) If A*⇒ x1Ax2 and If A*⇒ x3Ax4 then x1 and x3 consist of the same type of symbol. Likewise x2 and x4. Otherwise Property 1 above would be violated. 5) If A*⇒ x1Ax2 then either a) x1 consists solely of a's and x2 solely of b’s or of d’s, b) x1 consists solely of b's and x2 solely of c’s or c) x1 consists solely of c's and x2 solely of d’s. In any of the other cases it is easy to derive a string not in L. Thus the variables other than S can be divided into four classes, Cab, Cad, Cbc, and Ccd. Cab is the set of all A in V such that A*⇒ x1Ax2 with x1 in a* and x2 in b*; Cad, Cbc, and Ccd are defined analogously. 6) A derivation containing a symbol in Cab or Ccd cannot contain a symbol in Cad or Cbc or vice versa. Otherwise, we could increase the number of three types of symbols of a sentence in L without increasing the number of the fourth type of symbol. In that case, there would be a sentence in L for which the number of occurrences of one type of symbol is smaller than that of any other. We now note that if a derivation contains a variable in Cab or Ccd, then the terminal string generated must be in {anbncmdm | n ≥ 1, m ≥ 1}. For assume that A in Cab appears in a derivation of a sentence x not in {anbncmdm | n ≥ 1, m ≥ 1}. 53 | P a g e Then x must be of the form anbmcmdn, m ≠ n. Since A is in Cab, a sentence an + pbm + pcmdn, m ≠ n, for some p > 0, could be generated. Such a sentence is not in L. A similar argument holds for A in Ccd. Similar reasoning implies that if a derivation contains a variable in Cad or Cbc, then the sentence generated must be in {anbmcmdn | n ≥ 1, m ≥ 1}. We divide G into two grammars, G1 = ({S} ∪ Cab ∪ Ccd, T, P1, S) and G2 = ({S} ∪ Cad ∪ Cbc, T, P2, S) where P1 contains all productions of P with a variable form Cab or Ccd on either the right or left, and P2 contains all productions of P with a variable from Cad or Cbc on either the right or left. In addition, P1 contains all productions from P of the form S → anbncmdm, n ≠ m. and P2 contains all productions from P of the form S → anbmcmdn, , n ≠ m. Productions of P of the form S → anbncndn are not in either P1 or P2. Since G generates {anbncmdm | n ≥ 1, m ≥ 1} ∪ {anbmcmdn | n ≥ 1, m ≥ 1} G1 must generate all sentences in {anbncmdm | n ≥ 1, m ≥ 1, n ≠ m} plus possibly some sentences in {anbncndn | n ≥ 1}, and G2 must generate all sentences in {anbmcmdn | n ≥ 1, m ≥ 1, , n ≠ m} plus possibly some sentences in {anbncndn | n ≥ 1}. We now show that this cannot be the case unless G1 and G2 both generate all but a finite number of sentences in {anbncndn | n ≥ 1} are generated by both G1 and G2 and hence by two distinct derivations in G. This contradicts the assumption that G was unambiguous. To see that G1 and G2 generate all but a finite number of sentences in {anbncndn | n ≥ 0}, number the productions in Pl of the form S → α from 1 to r. For 1 ≤ i ≤ r, if S → α is the ith production, let Ni be the set of all n such that S ⇒G1 α *⇒G1 anbncmdm for some m, and let Mi be the set of all m such that S ⇒G1 α *⇒G1 anbncmdm for some n. We leave it to the reader to show that for any n in Ni and any m in Mi, S ⇒G1 α *⇒G1 anbncmdm. 54 | P a g e A similar argument applies to G2. The reader can easily show that G2 cannot have a right side with two or more variables. We number certain productions and pairs of productions in a single ordering. Productions of the form S → α1Bα2, where B is in Cbc, will receive a number, and if this number is i, let Ni be the set of all n such that for some m, S ⇒ α1Bα2 *⇒ anbmcmdn. Also let Mi be the set of m such that for some n, S ⇒ α1Bα2 *⇒ anbmcmdn. The pair of productions S → α amd A → α1Bα2 will receive a number if α contains a variable in Cad, A is in Cad, and B is in Cbc. If this pair is assigned the number i, then define Ni to be the set of n such that for some m, S ⇒ α *⇒ x1 Ax2 ⇒ x1α1Bα2x2 *⇒ anbmcmdn Also define Mi to be the set of m such that for some n, S ⇒ α *⇒ x1 Ax2 ⇒ x1α1Bα2x2 *⇒ anbmcmdn Once again, for any n in Ni and m in Mi, S *⇒G1 anbmcmdn, and thus it follows from Lemma 4.5 that G2 generates all but a finite number of sentences in {anbncndn | n ≥ 1}. We conclude that for some n, anbncndn is in both L(G1) and L(G2). This sentence has two leftmost derivations in G. Exercises: 1. Give Context-free grammars generating the following sets. a. The set of palindromes (strings that read the same forward as backward) over alphabet {a,b}. b. The set of all strings over alphabet {a,b} with exactly twice as many a’s and b’s. 2. Let G be the grammar S->bS|bScS|ε. Prove that L(G) = {x|each prefix of x has at least as many b’s as c’s} 3. The grammar E -> E + E | E * E |(E)|id Generates the set of arithmetic expressions with +, *, parenthesis and id. The grammar is ambiguous ince if _ id * id can be generated by two distinct leftmost derivations. Construct an equivalent unambiguous grammar. 4. Find a CG with no useless symbols equivalent to S-> AB|CA, A->a, B-> BC|AB, C-> aB|b 5. Find a GNF grammar equivalent to the ff CFG: S-> AA|0 A -> SS|1 55 | P a g e 5.0 PUSHDOWN AUTOMATA Overview This section will discuss a computational tool called pushdown automaton (PDA). This will allow the student to understand the equivalence of CFGs and PDAs, that both accept the context free language. Objectives: At the end of this section, the student is expected to be able to: 1. Derive a sentence using production rules in PDA 2. Discuss the difference of accepting a sentence by empty stack and final state. 3. Create a mode from a given CFL and vice versa 5.1 INFORMAL AND FORMAL DEFINITIONS The pushdown automaton is essentially a finite automaton with control of both an input tape and a stack, or "first in-last out" list. That is, symbols may be entered or removed only at the top of the list. When a symbol is entered at the top, the symbol previously at the top becomes second from the top, the symbol previously second from the top becomes third, and so on. Similarly, when a symbol is removed from the top of the list, the symbol previously second from the top becomes the top symbol, the symbol previously third from the top becomes second, and so on. 56 | P a g e  Finite control for pushdown automaton accepting {wcwR | w in (0+1)*} The PDA will have an input tape, a finite control, and a stack. When a stack is empty, the string is accepted if the entire tape was read. A pushdown automaton M = (Q, ∑, Γ, δ, q0, Z0, F), where Q is a finite set of states ∑ is the input alphabet Γ is the stack alphabet q0 in Q is the initial state Z0 in Γ is the start symbol F ⊆ Q is the set of final states δ: Q x (∑ ∪ {є}) x Γ ⇒ subsets of Q x Γ* Moves δ(q, a, Z) = {(p1, γ1), (p2, γ2), …, (pm, γm)} δ(q, є, Z) = {(p1, γ1), (p2, γ2), …, (pm, γm)} 57 | P a g e  Formal PDA accepting {wcwR | w in (0+1)*} by empty stack Instantaneous Descriptions If M = (Q, ∑, Γ, δ, q0, Z0, F) is a PDA, we say (q, aw, Zα) ⊦ (p, w, βα) if δ(q, a, Z) contains (p, β) where a may be є. (Note that ⊦ means “leads to”) Example: The fact that (q1, BG) is in δ(q1, 0, G) tells us that (q1, 011, GGR) ⊦ (q1, 11, BGGR) I ⊦* I, I ⊦i K I ⊦ J and J ⊦* K imply I ⊦* K Accepted Languages For PDA M = (Q, ∑, Γ, δ, q0, Z0, F) we define L(M), the language accepted by final state, to be {w | (q0, w, Z0) ⊦* (p, є, γ) for some p in F, γ in Γ* where p is the final state and γ is a string of stack symbols We define N(M), the language accepted by empty stack (or null stack) to be {w | (q0, w, Z0) ⊦* (p, є, є) for some p in Q}. 58 | P a g e  A nondeterministic PDA that accepts {wwR | w in (0+1)*} Deterministic PDA’s A PDA M = (Q, ∑, Γ, δ, q0, Z0, F) is deterministic if: 1) For each q in Q and Z in Γ, whenever δ(q, є, Z) is nonempty, then δ(q, a, Z) is empty for all a in ∑; 2) For no q in Q, Z in Γ, and a in ∑ ∪ {є} does δ(q, a, Z) contain more than one element. 59 | P a g e 5.2 PUSHDOWN AUTOMATA AND CONTEXT-FREE LANGUAGES Equivalence of acceptance by final state and empty stack Theorem 5.1 If L is L(M2) for some PDA M2 then L is N(M1) for some PDA M1. Let M2 = (Q, ∑, Γ, δ, q0, Z0, F) be a PDA such that L = L(M2) (Accept by Final State) Let M1 = (Q ∪ {qe, q’0}, ∑, Γ ∪ {X0}, δ’, q’0, X0, Ø) (Accept by Empty Stack) where, (1) δ’(q’0, є, X0) = {(q0, Z0, X0)} (2) δ’(q, a, Z) = δ(q, a, Z) for all q in Q, a, and, z (3) δ’(q, є, Z) = {(qe, є)} for all q in F, Z in Γ ∪ {X0} (4) δ’(qe, є, Z) = {(qe, є)} for all Z in Γ ∪ {X0} Result is a new PDA which accepts empty stack. Theorem 5.2 If L is N(M1) for PDA M1, then L is L(M2) for some PDA M2. Let M1 = (Q, ∑, Γ, δ, q0, Z0, Ø) be a PDA such that L = N(M1) (Accept by Empty Stack) Let M1 = (Q ∪ {q’0, qf}, ∑, Γ ∪ {X0}, δ’, q’0, X0, qf) (Accept by Final State) where (1) δ’(q’0, є, X0) = {(q0, Z0, X0)} (2) δ’(q, a, Z) = δ(q, a, Z) for all q in Q, a in ∑ ∪ {є} , and Z in Γ (3) δ’(q, є, X0) = {(qf, є)} for all q in Q Example: Consider the PDA M1 = ({q, p}, {a, b}, {X, Y}, δ, X, Ø) where δ(q, a, X) = {(q, YX)} δ(p, a, X) = {(p, XX)} δ(q, є, X) = {(p, є)} δ(p, b, X) = {(q, є)} δ(q, b, Y) = {(q, є)} 60 | P