Are the following True or False. In either case, provide a justification for you

Question

Are the following True or False. In either case, provide a justification for your answer.

a) A regular expression can be writen for any context free language.

b) There exist regular languages that are not also context-free.

c) Unlike regular languages, all context-free languages are infinite in size.

d) Unlike regular languages, context-free languages may include infinite-length strings.

e) Like the strong pumping lemma for regular languages, the strong pumping lemma for context-free languages allows us to only consider partitions involving the first (p) symbols (where p is the pumping length).

Explanation / Answer

a) A regular expression cannot be written for any context free language because all regularlanguages are context-free but all context-free languages are not regular .(By Chomsky's Hierarchy). So false

b) False. All regular languages are context free because the regular grammar that generates a regular language is a subset of the productions of the context free grammar that generates Context free language.

c) True. Regular language is finite in size but Context free language also is infinite in size by Pumping Lemma for regular languages.

d)True. context free languages can include infinite length strings only when length of the string is greater than 2n-1 but regular languages cannot generate strings of infinite length because kleene closure of a regular expression can generate only finite length strings.

e) True because |vwx|<=p where s=uvwxy.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.