Equivalence of CFGs and PDAs in Formal Language Theory
Context-free grammars (CFGs), context-free languages (CFLs), and pushdown automata (PDAs) play crucial roles in formal language theory. Understanding the equivalence between CFGs and PDAs, proving languages not context-free, and applying the pumping lemma for CFLs are key concepts covered in this material.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
18.404/6.840 Lecture 5 Last time: - Context free grammars (CFGs) - Context free languages (CFLs) - Pushdown automata (PDA) - Converting CFGs to PDAs Today: (Sipser 2.3, 3.1) - Proving languages not Context Free - Turing machines - T-recognizable and T-decidable languages 1
Equivalence of CFGs and PDAs Recall Theorem: ? is a CFL iff some PDA recognizes ? Done. Need to know the fact, not the proof Corollaries: 1) Every regular language is a CFL. 2) If ? is a CFL and ? is regular then ? ? is a CFL. Proof sketch of (2): While reading the input, the finite control of the PDA for ? simulates the DFA for ?. Note 1: If ? and ? are CFLs then ? ? may not be a CFL (will show today). Therefore the class of CFLs is not closed under . Note 2: The class of CFLs is closed under , , (see Pset 2). 2
Proving languages not Context Free Let ? = 0?1?2? ? 0}. We will show that ?isn t a CFL. Pumping Lemma for CFLs: For every CFL ?, there is a ? such that if ? ? and ? ? then ? = ????? where 1) ??????? ? for all ? 0 2) ?? 3) ??? ? ? ? ? ? ? ? ? ? = Informally: All long strings in ? are pumpable and stay in ?. ? ? ? ? ? ? ? ? ? 3
Pumping Lemma Proof Pumping Lemma for CFLs: For every CFL ?, there is a ? such that if ? ? and ? ? then ? = ????? where 1) ??????? ? for all ? 0 2) ?? 3) ??? ? E Proof by picture: R E E R R ? ? ? ? R R ? ? ? ? ? ? Generates ??????? = ??2??2? Generates ??? = ??0??0? R ? = ? ? ? ? Long ? tall parse tree ? cutting and pasting argument 4
Pumping Lemma Proof details For ? ? where ? ?, we have ? = ????? where: 1) ??????? ? for all ? 0 cutting and pasting 2) ?? start with the smallest parse tree for ? 3) ??? ? pick the lowest repetition of a variable Let ? = the length of the longest right hand side of a rule (E E+T) = the max branching of the parse tree Let = the height of the parse tree for ?. E E E + T A tree of height and max branching ? has at most ? leaves. So ? ? . want > ? R Let ? = ??+ 1 where ? = # variables in the grammar. R So if ? ? > ?? then ? > ?|?| and so > ? . Thus at least ? + 1 variables occur in the longest path. So some variable ? must repeat on a path. ? = ? ? ? ? ? use ? > ?? set ? = ??+ 1 5
Example 1 of Proving Non-CF Pumping Lemma for CFLs: For every CFL ?, there is a ? such that if ? ? and ? ? then ? = ????? where 1) ??????? ? for all ? 0 2) ?? 3) ??? ? Let ? = 0?1?2? ? 0} Show: ? is not a CFL Proof by Contradiction: Assume (to get a contradiction) that ? is a CFL . The CFL pumping lemma gives ? as above. Let ? = 0?1?2? ?. Pumping lemma says that can divide ? = ????? satisfying the 3 conditions. Condition 3 ( ??? ?) implies that ??? cannot contain both 0s and 2s. So ??2??2? has unequal numbers of 0s, 1s, and 2s. Thus ??2??2? ?, violating Condition 1. Contradiction! Therefore our assumption (? is a CFL) is false. We conclude that ? is not a CFL . c) The class of CFLs is closed under complement. Check-in 5.1 Let ?1= 0?1?2? ?,? 0} (equal #s of 0s and 1s) Let ?2= 0?1?2? ?,? 0} (equal #s of 1s and 2s) Observe that PDAs can recognize ?1 and ?2. What can we now conclude? a) The class of CFLs is not closed under intersection. b) The Pumping Lemma shows that ?1 ?2 is not a CFL . ? = 00 0011 1122 22 ? ? ? ? ? ? Check-in 5.1 6
Example 2 of Proving Non-CF Pumping Lemma for CFLs: For every CFL ?, there is a ? such that if ? ? and ? ? then ? = ????? where 1) ??????? ? for all ? 0 2) ?? 3) ??? ? Let ? = ?? ? } . = {0,1}. Show: ? is not a CFL. ?1= 000 001000 001 ? ? Assume (for contradiction) that ? is a CFL. The CFL pumping lemma gives ? as above. Need to choose ? ?. Which ?? Try ?1= 0?10?1 ?. But ?1 can be pumped and stay inside ?. Bad choice of ?. Try ?2= 0?1?0?1? ?. Show ?2 cannot be pumped ?2= ????? satisfying the 3 conditions. Condition 3 implies that ??? does not overlap two runs of 0s or two runs of 1s. Therefore, in ??2??2?, two runs of 0s or two runs of 1s have unequal length. So ??2??2? ? violating Condition 1. Contradiction! Thus ? is not a CFL. ? ? ? ?2= 0 01 10 01 1 ? ? ? ? ? 7
Turing Machines (TMs) head . . . a b a b b Finite control read/write input tape 1) 2) 3) 4) 5) Head can read and write Head is two way (can move left or right) Tape is infinite (to the right) Infinitely many blanks follow input Can accept or reject any time (not only at end of input) 8
TM example TM recognizing ? = a?b?c? ? 0 Scan right until while checking if input is in a b c , reject if not. 2) Return head to left end. 3) Scan right, crossing off single a, b, and c. 4) If the last one of each symbol, accept. 5) If the last one of some symbol but not others, reject. 6) If all symbols remain, return to left end and repeat from (3). 1) head input tape b b a a a c c c b Finite control accept Check-in 5.2 How do we get the effect of crossing off with a Turing machine? a) We add that feature to the model. b) We use a tape alphabet = {a, b, c, a, b, c, }. c) All Turing machines come with an eraser. Check-in 5.2 9
TM Formal Definition Defn: Defn: A Turing Machine (TM) is a 7-tuple (?, , ,?,?0,?acc ,?rej) input alphabet tape alphabet ( ) ?: Q ? {L, R} (L = Left, R = Right) ? ?,a = (?,b, R) On input ? a TM ? may halt (enter ?acc or ?rej) or ?may run forever ( loop ). Check-in 5.3 This Turing machine model is deterministic. How would we change it to be nondeterministic? a) Add a second transition function. b) Change ? to be ?: Q ?( ? {L, R} ) c) Change the tape alphabet to be infinite. So ? has 3 possible outcomes for each input ?: 1. Accept? (enter ?acc ) 2. Reject ? by halting (enter ?rej ) 3. Reject ? by looping (running forever) 10 Check-in 5.3
TM Recognizers and Deciders Let ? be a TM. Then ? ? = ? ?accepts ?}. Say that ?recognizes?if? = ?(?). Defn:?is Turing-recognizable if ? = ?(?) for some TM ?. Defn: TM ? is a decider if ? halts on all inputs. T-recognizable Say that ?decides?if? = ?(?) and ? is a decider. Defn:?is Turing-decidable if ? = ?(?) for some TM decider ?. T-decidable CFLs regular 11
Quick review of today 1. 1. Proved the CFL Pumping Lemma as a tool for Proved the CFL Pumping Lemma as a tool for showing that languages are not context free. showing that languages are not context free. 2. 2. Defined Turing machines (TMs). Defined Turing machines (TMs). 3. 3. Defined TM deciders (halt on all inputs). Defined TM deciders (halt on all inputs). 4. 4. T T- -recognizable and T recognizable and T- -decidable languages. decidable languages. 12
MIT OpenCourseWare https://ocw.mit.edu 18.404J Theory of Computation Fall 2020 For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.
