Consider the language L1 - 0i1j - i- j- L2 - 0i1j i-j- L3 - 0i1j - i-2j-1- L4 - 0i1j - i-2j-Which of the following statements is true-

L_1=0^i;1^j;i≠ j L_2=0^i;1^j;i = j L_3=0^i;1^j;i = 2j+1 L_4=0^i;1^j;i ≠ 2j All of nbsp; nbsp;L_1,L_2,L_3 and nbsp;L_4 are context free,since ,each of thes ...

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

Byju's Answer

Other

Objective Session 3

Consider the ...

Question

Consider the language L1 = { $0^{i} 1^{j} | i \neq j$ }, L2 = { $0^{i} 1^{j} i = j$ }, L3 = $0^{i} 1^{j} | i = 2 j + 1$ }, L4 = { $0^{i} 1^{j} | i \neq 2 j$ }.
Which of the following statements is true?

All are context free

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Only L1 and L2 are context free

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Only L2 is context free

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Only L2 and L3 are context free

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A All are context free
$L_{1}$ ={ $0^{i}; 1^{j}; i \neq j$ }
$L_{2}$ ={ $0^{i}; 1^{j}; i = j$ }
$L_{3}$ ={ $0^{i}; 1^{j}; i = 2 j + 1$ }
$L_{4}$ ={ $0^{i}; 1^{j}; i \neq 2 j$ }
All of $L_{1}$ , $L_{2}$ , $L_{3}$ and $L_{4}$ are context free,since ,each of these languages has a single linear comparision between i and j and any linear comparison between i and j can be perfomed,in a PDA.

Suggest Corrections

Similar questions

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. Consider the two languages

L_{1} and L 2

where

L_{1}

is regular and

L_{2}

D C F L .

Then the language

L_{3} = (L_{1} \cap L_{2}^{*})^{'}

is/are true about

L_{3}

Q. Let the number of strings in the following

L_{1} = 0^{*} 1^{*}, L_{2} = 1^{*} 0^{*}, L_{3} = (0 + 1)^{*} and L_{4} = 0^{*} 1^{*} 0^{*} .

language are_____

L = (L_{1} \cap L_{2}) - (L_{3} \cap L_{4})

Q. Consider the following languages.

L_{1} =

{

a^{i} b^{j} c^{k} | i = j, k \geq 1

}

L_{2} =

{

a^{i} b^{j} | j = 2 i, i \geq 0

}
Which of the following is true?

Q. Let L =

L_{1} \cap L_{2}

, where

L_{1} a n d L_{2}

are languages as defined below:

L_{1}

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

}

L_{2}

a^{i} b^{j} c^{k} | i, j, k \geq 0

}
Then L is

Join BYJU'S Learning Program

Consider the language L1 = {0i1j | i≠j}, L2 = {0i1j i=j}, L3 = 0i1j | i=2j+1}, L4 = {0i1j | i≠2j}. Which of the following statements is true?

The correct option is A All are context freeL1={0i;1j;i≠j} L2={0i;1j;i=j} L3={0i;1j;i=2j+1} L4={0i;1j;i≠2j} All of L1,L2,L3 and L4 are context free,since ,each of these languages has a single linear comparision between i and j and any linear comparison between i and j can be perfomed,in a PDA.

Consider the language L1 = { $0^{i} 1^{j} | i \neq j$ }, L2 = { $0^{i} 1^{j} i = j$ }, L3 = $0^{i} 1^{j} | i = 2 j + 1$ }, L4 = { $0^{i} 1^{j} | i \neq 2 j$ }.
Which of the following statements is true?