Theory of Compu...

If L₁ and L₂ are context free language, then which of the following is not necessarily a context free language?

Consider the grammar G = {{S, X, Y}, {x, y}, S, P} with P given as

S → SXSYS | SYSXS | ϵ

X → x

Y → y

The language {a^mbⁿc^m+n | m, n ≥ 1} is:

Which of the following grammar is in Greibach Normal Form?

A. S → AB, A → a, B → b

B. S → aA | A → ϵ

C. S → Aa, A → a

Which of the following statements is true?

S1: If L is a context-free language and R is a regular language, L-R is not necessarily a context-free language.

S2: The context-free languages are closed under positive closure.

S3: The context-free languages are not closed under reversal.

Which of the following language L is/are not a deterministic context free grammar?

I. L = {wcw^r : w ϵ {a, b}^*}

II. L = {aⁿb^mc^p, n = m or m = p}

III. L = {ww^r : w ϵ {a, b}^* }

Consider the following grammars:

G₁ : S → aSb|bSa|aa

G₂ : S → aSb|bSa|SS|λ

G₃ : S → aSb|bSa|SS|a

G₄ : S → aSb|bSa|SS|SSS|λ

What is the minimum number of productions present in the below given context free grammar to make it Chomsky Normal Form?

S → XYx

X → xxy

Y → Xz

Which of the following is/are false about the context free grammar if L₁ is context free language and L^R₁ be its reversal also L₂ is deterministic context free language (DCFL) and L^R₁ be its reversal language?

I. L^R₁ is not a CFL

II. L^R₂ is a DFCL

III. L^R₁ ∪ L^R₂ is a CFL

Which of following problems are undecidable?

I. Membership problem in context-free languages

II. Whether a given context-free language is regular

III. Whether a finite state automation halts on all inputs