Consider the language {ww | w element {a, b}*}. Show it is not regular via Pumpi
ID: 3862027 • Letter: C
Question
Consider the language {ww | w element {a, b}*}. Show it is not regular via Pumping Theorem Show it is not regular via the Mayhill NE rode theorem Show it is not Context-free via Pumping. Show that any DFA M = (K, sigma, delta, s, F) accepts an infinite language if it accepts some string w with | w | > | K|. Similarly show that a CFG G = (V, sigma, R, S) generates an infinite language if it generates a string longer than fan-out^|v| - where for grammar G its fan-out = Max {|w|; A rightarrow w element R}, the maximal length of the right-hand sides of rules.Explanation / Answer
3 a)
b) Let S = { an | n }. This set is infinite because it contains one string for each natural number. Now, consider any an , am S where an am. Then anan L and aman L, so an and am are distinguishable relative to L. Thus S is an infinite set of strings that are all distinguishable relative to L. Therefore, by the Myhill-Nerode Theorem, L is not regular
c)