Which of the following languages are context-free- L1- ambnanbm-m-n- 1 L2- ambnambn-m-n- 1 L3- ambn- m-2n-1

nbsp; L_1={ a^mb^na^nb^m|m,n≥ 1 } is CFL (push "a" and "b" and then first "a" pops "b" and then "b" pops "a"). nbsp; L_2={ a^mb^na^mb^n|m,n≥ 1 } is non CF ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Byju's Answer

Standard XII

Mathematics

Theorems for Differentiability

Which of the ...

Question

Which of the following languages are context-free?
$L_{1} = {a^{m} b^{n} a^{n} b^{m} | m, n \geq 1}$
$L_{2} = {a^{m} b^{n} a^{m} b^{n} | m, n \geq 1}$
$L_{3} = {a^{m} b^{n} | m = 2 n + 1}$

Open in App

Solution

$L_{1} = {a^{m} b^{n} a^{n} b^{m} | m, n \geq 1}$ is CFL (push "a" and "b" and then first "a" pops "b" and then "b" pops "a").
$L_{2} = {a^{m} b^{n} a^{m} b^{n} | m, n \geq 1}$ is non-CFL (Alternate comparision not possible in a PDA)
$L_{3} = {a^{m} b^{n} | m = 2 n + 1}$ is CFL (Single comparison is possible in a PDA)

Suggest Corrections

Similar questions

L e t L_{1} =

{

0^{n + m} 1^{n} 0^{m} | n, m \geq 0

L_{2} =

{

0^{n + m} 1^{n + m} 0^{m} | n, m \geq 0

}, and

L_{3} =

{

0^{n + m} 1^{n + m} 0^{n + m} | n, m \geq 0

}.
Which of these languages are NOT context-free?

Q. Consider the following languages:

L_{1} = {a^{p} | p i s a p r i m e n u m b e r}

L_{2} = {a^{n} b^{m} c^{2 m} | n \geq 0, m \geq 0}

L_{3} = {a^{n} b^{n} c^{2 n} | n \geq 0}

L_{4} = {a^{n} b^{n} | n \geq 1}

Which of the following are CORRECT?
I.

L_{1}

is context-free but not regular.
II

L_{2}

is context-free.
III.

L_{3}

is not context-free but recursive.
IV.

L_{4}

is deterministic context-free.

Q. Consider the following types of languages

L_{1} : R e g u l a r, L_{2} : C o n t e x t - f r e e, L_{3} : R e c u r s i v e, L_{4} : R e c u r s i v e l y e n u m e r a b l e .

Which of the following is/are TRUE?
I.

_{3} \cup L_{4}

is recursively enumerable.
II.

_{2} \cup L_{3}

is recursive.
III.

_{1} \cap L_{2}

is context-free.
IV.

L_{1} \cup_{2}

is context-free.

Q. Let

L_{1} L_{2}

be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?
I.

L_{1} \cup L_{2}

is context-free.
II.

_{1}

is context-free.
III.

L_{1} - R

is context-free.
IV.

L_{1} \cap L_{2}

is context-free.

Q. Let

L_{1}

be a regular language and

L_{2}

be a context-free language. Which of the following languages is/are context-free?

Join BYJU'S Learning Program

Which of the following languages are context-free? L1={ambnanbm|m,n≥1} L2={ambnambn|m,n≥1} L3={ambn| m=2n+1}

L1={ambnanbm|m,n≥1} is CFL (push "a" and "b" and then first "a" pops "b" and then "b" pops "a"). L2={ambnambn|m,n≥1} is non-CFL (Alternate comparision not possible in a PDA) L3={ambn| m=2n+1} is CFL (Single comparison is possible in a PDA)

Which of the following languages are context-free?
$L_{1} = {a^{m} b^{n} a^{n} b^{m} | m, n \geq 1}$
$L_{2} = {a^{m} b^{n} a^{m} b^{n} | m, n \geq 1}$
$L_{3} = {a^{m} b^{n} | m = 2 n + 1}$