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

Answer:

a) FALSE , we csn write regular language to context free language only if it is regular.

b) FALSE , all regular languages are context free. Not all context free languages are regular.

c) FALSE , Context free languages are done with push down automata and PDA is having a finite stack . So false.

d) TRUE, some context free languages can include infinite length strings

RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

THANK YOU!!

e) TRUE, both uses the same logic with different cases.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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