3. Consider the language {www = {a, b}*}. a) Show it is not regular via Pumping...

 

Transcribed Image Text:

3. Consider the language {www = {a, b}*}. a) Show it is not regular via Pumping Theorem b) Show it is not regular via the Myhill-Nerode theorem c) Show it is not Context-free via Pumping. 4. Show that any DFA M = (K, E, 8, s, F) accepts an infinite language if it accepts some string w with |w| > |KI. Similarly show that a CFG G = (V, E, R, S) generates an infinite language if it generates a string longer than fan-out IVI - where for grammar G its fan-out = Max {[w]: Awe R}, the maximal length of the right hand sides of rules. 3. Consider the language {www = {a, b}*}. a) Show it is not regular via Pumping Theorem b) Show it is not regular via the Myhill-Nerode theorem c) Show it is not Context-free via Pumping. 4. Show that any DFA M = (K, E, 8, s, F) accepts an infinite language if it accepts some string w with |w| > |KI. Similarly show that a CFG G = (V, E, R, S) generates an infinite language if it generates a string longer than fan-out IVI - where for grammar G its fan-out = Max {[w]: Awe R}, the maximal length of the right hand sides of rules.