Identify-Class-Language

Question 1

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
Theory-of-ComputationIdentify-Class-LanguageGATE 1996
Question 1 Explanation: 
Context free languages are not closed under intersection.
Question 2

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
Theory-of-ComputationIdentify-Class-LanguageGATE 1996
Question 2 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 3

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
Theory-of-ComputationIdentify-Class-LanguageGATE 1999
Question 3 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.
Question 4

Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?

A
L = 0+
B
L is regular but not 0+
C
L is context free but not regular
D
L is not context free
Theory-of-ComputationIdentify-Class-LanguageGATE 2000
Question 4 Explanation: 
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
There are 4 questions to complete.

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

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