Identify-Class-Language
Question 1 |
Consider the languages L1,L2 and L3 as given below.
- L1 = {0p1q|p,q∈N},
L2 = {0p1q|p,q∈N and p=q} and
L3 = {0p1q0r|p,q,r∈N and p=q=r}.
Which of the following statements is NOT TRUE?
Push Down Automate (PDA) can be used to recognize L1 and L2 | |
L1 is a regular language | |
All the three languages are context free | |
Turing machines can be used to recognize all the languages |
Question 1 Explanation:
L1: regular language
L2: context free language
L3: context sensitive language
L2: context free language
L3: context sensitive language
Question 2 |
If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?
L1, L2 | |
L1 ∩ L2 | |
L1 ∩ R | |
L1 ∪ L2 |
Question 2 Explanation:
Context free languages are not closed under intersection.
Question 3 |
Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
L = {x|x has an equal number of a's and b's } is regular | |
L = {anbn|n≥1} is regular | |
L = {x|x has more a's and b's} is regular | |
L = {ambn|m ≥ 1, n ≥ 1} is regular |
Question 3 Explanation:
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Here, m and n are independent.
So 'L' Is Regular.
Question 4 |
If L is context free language and L2 is a regular language which of the following is/are false?
L1 – L2 is not context free | |
L1 ∩ L2 is context free | |
~L1 is context free | |
~L2 is regular | |
Both A and C |
Question 4 Explanation:
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection. So True.
(C) CFL is not closed under complementation. Hence False.
(D) Regular language is closed under complementation.
Hence True.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection. So True.
(C) CFL is not closed under complementation. Hence False.
(D) Regular language is closed under complementation.
Hence True.