0 votes 0 votes Is the following language CFL : { ww | w in (a+b)* and |w| <1000 } Theory of Computation context-free-language theory-of-computation context-free-grammar pushdown-automata + – practicalmetal asked Mar 20, 2023 practicalmetal 555 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shreyas Namjoshi commented Apr 8, 2023 reply Follow Share since the given language is havinga restriction on length of strings , i.e |w | < 1000 so maximum length of the string generated by this grammar is 1998 since there is limit to length the language generated by this grammar will be regular, but according to Chomsky Hierarchy all Regular languages are Context Free also therefore given Language is Context Free Language. 0 votes 0 votes ByteCode commented Jan 19 reply Follow Share Use Pumping Lemma for context free language to deduce your answer 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Answer is Yes. If we don’t have the condition |w| < 1000 it is not a CFL. And we are adding a restriction of length to it it will make the language finite and hence regular and CFL. https://stackoverflow.com/questions/42611602/is-ww-where-w-belongs-to-a-b-a-context-free-language himalay answered Mar 25, 2023 • edited Mar 27, 2023 by himalay himalay comment Share Follow See 1 comment See all 1 1 comment reply gatecse commented Mar 26, 2023 reply Follow Share That’s wrong. Because the restriction is actually making the number of possible strings to be finite and hence the language bcomes finite, hence regular and hence CFL too. 3 votes 3 votes Please log in or register to add a comment.