18.404/6.840 Lecture 3 Last time: – Nondeterminism – NFA → DFA

18.404/6.840 Lecture 3 Last time: - Nondeterminism - NFA DFA - Closure under and - Regular expressions finite automata Today: (Sipser §1.4 – §2.1) - Finite automata regular expressions - Proving languages aren’t regular - Context free grammars We start counting Check-ins today. Review your email from Canvas. Homework due Thursday. 1

DFAs Regular Expressions Recall Theorem: If is a regular expressipn and then is regular Proof: Conversion NFA DFA 𝑀 Regular expression Finite automaton Recall: we did as an example Today’s Theorem: If is regular then for some regular expr Proof: Give conversion DFA WAIT! Need new concept first. 2

Generalized NFA Defn: A Generalized Nondeterministic Finite Automaton (GNFA) is similar to an NFA, but allows regular expressions as transition labels a a b ab 𝐺1 𝑞1 a b 𝑞2 For convenience we will assume: - One accept state, separate from the start state b 𝑞3 ε - One arrow from each state to each state, except a) only exiting the start state b) only entering the accept state aab ε 𝑞4 We can easily modify a GNFA to have this special form. 3

GNFA Regular Expressions Lemma: Every GNFA has an equivalent regular expression Proof: By induction on the number of states of Basis : 𝐺 ¿ 𝑟 Remember: is in special form Let Induction step : Assume Lemma true for states and prove for states IDEA: Convert -state GNFA to equivalent -state GNFA GNFA GNFA states states 4

-state GNFA (—1)-state GNFA Check-in 3.1 𝑥 𝑟2 𝑥 𝑟 1 showed𝑟 how We just to convert GNFAs to regular expressions 3 but𝑞our goal was to show that how 𝑞 to𝑖 convert DFAs𝑞to 𝑞 𝑖 𝑗 𝑟4 𝑟 1 ( 𝑟 2 ) 𝑟 3 𝑟 4 𝑗 regular expressions. How do we finish our goal? (a) Show how to convert DFAs to GNFAs (b) Show how to convert GNFAs to DFAs (c) We are already done. DFAs are a typestates of GNFAs. states Thus DFAs and regular expressions are equivalent. 1. Pick any state except the start and accept states. 2. Remove . 3. Repair the damage by recovering all paths that went through . 4. Make the indicated change for each pair of states . Check-in 3.1 5

Non-Regular Languages How do we show a language is not regular? - Remember, to show a language is regular, we give a DFA. - To show a language is not regular, we must give a proof. - It is not enough to say that you couldn’t find a DFA for it, therefore the language isn’t regular. Two examples: Here . ] ] ] 1. Let has equal numbers of 0s and 1s Intuition: is not regular because DFAs cannot count unboundedly. ] ] 2. Let has equal numbers of 01 and 10 substrings 0101 0110 Intuition: is not regular because DFAs cannot count unboundedly. However is regular! Sometimes intuition works, but it can also be wrong. 6

Method for Proving Non-regularity } Pumping Lemma: For every regular language , there is a number (the “pumping length”) such that if and then where 1) for all 2) 𝑖 3) Informally: is regular every long string in can be Check-in 3.2pumped and the result stays in . Proof: Let DFA recognize . Let be the number of states in . Pick where . The Pumping Lemma depends on the fact that if has states and it runs for more than steps then 𝑦 𝑧 𝑥 𝑀 𝑦 𝑠 ¿ will enter some state at least twice. 𝑞𝑗 𝑞𝑗 The path that follows We call that fact: 𝑞 𝑗 will repeat a state when reading 𝑥 𝑧 when reading . (a) The Pigeonhole Principle because is so long. 𝑦 𝑦 𝑧 (b) Burnside's Counting Theorem 𝑥 The Coronavirus Calculation 𝑞𝑗 accepted 𝑞𝑗 𝑞 is also(c) 𝑗 7 Check-in 3.2

Example 1 of Proving Non-regularity Pumping Lemma: For every regular language , there is a such that if and then where 1) for all 2) 3) Let Show: is not regular Proof by Contradiction: Assume (to get a contradiction) that is regular. The pumping lemma gives as above. Let . Pumping lemma says that can divide satisfying the 3 conditions. But has excess 0s and thus contradicting the pumping lemma. Therefore our assumption ( is regular) is false. We conclude that is not regular. 8 𝑠 ¿ 000 000111 111 𝑥 𝑦 𝑝 𝑧

Example 2 of Proving Non-regularity Pumping Lemma: For every regular language , there is a such that if and then where 1) for all 2) 3) Let Say . 𝑠 ¿ 000 000000 000 Show: is not regular Proof by Contradiction: Assume (for contradiction) that is regular. The pumping lemma gives as above. Need to choose . Which ? Try . But that can be pumped and stay inside . Bad choice. Try . Show cannot be pumped satisfying the 3 conditions. Contradiction! Therefore is not regular. 9 𝑥 𝑦 𝑝 𝑧 𝑦 00 𝑠 ¿ 000 001000 001 𝑥 𝑦 𝑝 𝑧

Example 3 of Proving Non-regularity Variant: Combine closure properties with the Pumping Lemma. Let has equal numbers of 0s and 1s Show: is not regular Proof by Contradiction: Assume (for contradiction) that is regular. We know that is regular so is regular (closure under intersection). But and we already showed is not regular. Contradiction! Therefore our assumption is false, so is not regular. 10

Context Free Grammars 𝐺1 S 0S1 S R R } (Substitution) Rules Rule: Variable string of variables and terminals Variables: Symbols appearing on left-hand side of rule Terminals: Symbols appearing only on right-hand s Start Variable: Top left symbol In : 3Check-in rules 3.3 R,S 0,1 S 𝐺2 S RR Example of generating a string R 0R1 Tree of Resulting R S S substitutions Check all of the strings 0that S 1are 0inS1 (a) 001101 0 S 1 00S11 (b) 000111 R 00R11 (c) 1010 0011 𝐿 ( 𝐺1 ) (d) 𝐿 ( 𝐺 ) { 0 𝑘 1𝑘 𝑘 0 } Grammars generate strings 1. 2. 3. 4. string Write down start variable Replace any variable according to a rule Repeat until only terminals remain Result is the generated string is the language of all generated strings. 1 11 Check-in 3.3

Quick review of today 1. Conversion of DFAs to regular expressions Summary: DFAs, NFAs, regular expressions are all equivalent 2. Proving languages not regular by using the pumping lemma and closure properties 3. Context Free Grammars 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.