MyQuestionIcon

1

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

Consider the ...

Question

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.

Open in App

Solution

$L_{1} \to$ Regular, $L_{2} \to$ CFL
$L_{3} \to$ REC
$L_{4} \to$ RE
I. ${¯ L}_{3} \cup L_{4}$ is RE
${¯ L}_{3} \cup L_{4} = ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ R E C \cup R E = R E C \cup R E$
=RE $\cup R E = R E$
So I is true
II. ${¯ L}_{2} \cup L_{3}$ is recursive
${¯ L}_{2} \cup L_{3} = ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ C F L \cup R E C = ¯ ¯¯¯¯¯¯¯¯¯ ¯ C S L \cup R E C$
=CSL $\cup R E C$
=REC $\cup R E C = R E C$
So II is True.
III. $L_{1}^{} \cap L_{2}$ is CFL

$L_{1}^{} \cap L_{2}$ = $(R E G)^{*} \cap C F L$
$= R E G \cap C F L$ =CFL
So III is True
IV. $L_{1} \cup {¯ L}_{2}$ is CFL
$L_{1} \cup {¯ L}_{2} = R E G \cup ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ C F L = R E G \cup ¯ ¯¯¯¯¯¯¯¯¯ ¯ C S L$
$= R E G \cup C S L$ =CSL
Since, A CSL need not be a CFL,So IV is False
So only I,II and III are true.

Suggest Corrections

thumbs-up

0

Similar questions

Q. For any two language

L_{1} a n d L_{2}

L_{1}

is context free and

L_{2}

is recursively enumerable but not recursive, which of the following is/are necessarily true?
1.

_{1}

L_{1}

) is recursive
2.

_{2}

L_{2}

) is recursive
3.

_{1}

is context-free
4.

_{1} \cup L_{2}

is recursively enumerable

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. 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.

L_{1}

be a regular language and

L_{2}

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

Q. Let L₁be a recursive language. Let L₂ and L₃ be language that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Human Resources

Watch in App

Join BYJU'S Learning Program

CrossIcon