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

Inequalities

Consider the ...

Question

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.

Open in App

Solution

$L_{1} = {a^{p} | p p r i m e}$ is a CSL but not CFL (prime number checking involve division)
$L_{2} = {a^{n} b^{m} c^{2 m} | n \geq 0, m \geq 0}$ is CFL (one comparision)
$L_{3} = {a^{n} b^{n} c^{2 n} | n \geq 0}$ is CSL (two comparision)
$L_{4} = {a^{n} b^{n} | n \geq 1}$ is a DCFL
So,
I. $L_{1}$ is CFL but not regular is false.
II. $L_{2}$ is not CFL is false.
III. $L_{3}$ is not CFL but recursive is true since every CSL is recursive.
IV. $L_{4}$ is DCFL is true.
So, only III and IV are true and correct.

Suggest Corrections

Similar questions

L = {a^{n} | n > 0} \cup {a^{n} b^{n} | n \geq 0}

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 .

_{3} \cup L_{4}

_{2} \cup L_{3}

_{1} \cap L_{2}

L_{1} \cup_{2}

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

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}

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

L_{3} =

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

Join BYJU'S Learning Program