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?

A
Push Down Automate (PDA) can be used to recognize L1 and L2
B
L1 is a regular language
C
All the three languages are context free
D
Turing machines can be used to recognize all the languages
Question 1 Explanation: 
L1: regular 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?

A
L1, L2
B
L1 ∩ L2
C
L1 ∩ R
D
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?

A
L = {x|x has an equal number of a's and b's } is regular
B
L = {anbn|n≥1} is regular
C
L = {x|x has more a's and b's} is regular
D
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.
Question 4

If L is context free language and L2 is a regular language which of the following is/are false?

A
L1 – L2 is not context free
B
L1 ∩ L2 is context free
C
~L1 is context free
D
~L2 is regular
E
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.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access