IdentifyClassLanguage
Question 1 
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 
Not recursive
 
Regular
 
Context free but not regular  
Recursively enumerable but not context free 
Question 2 Explanation:
The strings in L_{1} are { c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L_{2} are { ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Question 3 
Which of the following is true for the language {a^{p}p is a prime} ?
It is not accepted by a Turing Machine
 
It is regular but not contextfree
 
It is contextfree but not regular
 
It is neither regular nor contextfree, but accepted by a Turing machine

Question 3 Explanation:
Finding prime number cannot be done by FA or PDA , so it cannot be regular or CFL. This language can be recognized by LBA , hence it can be accepted by Turing Machine.
Question 4 
Consider the following languages.
L_{1} = {a^{i} b^{j} c^{k}  i = j, k ≥ 1}
L_{1} = {a^{i} b^{j}  j = 2i, i ≥ 0}
Which of the following is true?
L_{1} is not a CFL but L_{2} is  
L_{1} ∩ L_{2} = ∅ and L_{1} is nonregular  
L_{1} ∪ L_{2} is not a CFL but L_{2} is  
There is a 4state PDA that accepts L_{1}, but there is no DPDA that accepts L_{2} 
Question 4 Explanation:
→ Both L_{1} and L_{2} are CFL. So option A is false.
→ L_{1} ∩ L_{2} = ∅, True and also L1 is nonregular. Option B is true.
→ L_{1} ∪ L_{2} is not a CFL but L_{2} is CFL is closed under union. So option C is false.
→ Both L_{1} and L_{2} accepted by DPDA.
→ L_{1} ∩ L_{2} = ∅, True and also L1 is nonregular. Option B is true.
→ L_{1} ∪ L_{2} is not a CFL but L_{2} is CFL is closed under union. So option C is false.
→ Both L_{1} and L_{2} accepted by DPDA.
Question 5 
Which of the following languages is (are) nonregular? L_{1} = {0^{m}1^{n}  0 ≤ m ≤ n ≤ 10000} L_{2} = {w  w reads the same forward and backward} L_{3} = {w ∊ {0, 1} *  w contains an even number of 0's and an even number of 1's}
L_{2} and L_{3} only  
L_{1} and L_{2} only  
L_{3} only  
L_{2} only 
Question 5 Explanation:
L_{1} and L_{3} are regular.
L_{1} is limited to fixed range and L_{3} contains even number of 0's which is regular. No need to use more memory to implement L_{3}.
L_{1} is limited to fixed range and L_{3} contains even number of 0's which is regular. No need to use more memory to implement L_{3}.
Question 6 
The language L = {0^{i}21^{i}  i≥0} over the alphabet {0,1, 2} is:
not recursive.  
is recursive and is a deterministic CFL.
 
is a regular language.
 
is not a deterministic CFL but a CFL.

Question 6 Explanation:
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.
Question 7 
Consider the following grammars. Names representing terminals have been specified in capital letters.
Which one of the following statements is true?
G_{1} is contextfree but not regular and G_{2} is regular  
G_{2} is contextfree but not regular and G_{1} is regular  
Both G_{1} and G_{2} are regular  
Both G_{1} and G_{2} are contextfree but neither of them is regular 
Question 7 Explanation:
Regular grammar is either right linear or left linear. A left linear grammar is one in which there is atmost 1 nontermial on the right side of any production, and it appears at the left most position.
Similarly, in right linear grammar, nonterminal appears at the right most position.
Here we can write a right linear grammar for G_{1} as
S → w(E
E → id)S
S → o
(wwhile, oother)
So, L(G_{1}) is regular.
Now for G_{2} also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G_{1} and G_{2} have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.
Similarly, in right linear grammar, nonterminal appears at the right most position.
Here we can write a right linear grammar for G_{1} as
S → w(E
E → id)S
S → o
(wwhile, oother)
So, L(G_{1}) is regular.
Now for G_{2} also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G_{1} and G_{2} have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.
Question 8 
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
L is recursively enumerable, but not recursive  
L is recursive, but not contextfree
 
L is contextfree, but not regular  
L is regular

Question 8 Explanation:
Let L_{1} = {s ∈ (0 + 1)*  d(s) mod5 = 2}, we can construct the DFA for this which will have 5 states (remainders 0,1,2,3,4)
L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
Question 9 
Let L_{1} be a regular language, L_{2} be a deterministic contextfree language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?
L_{1} ∩ L_{2} is a deterministic CFL  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is context free  
L_{1} ∩ L_{2} ∩ L_{3} is recursively enumerable 
Question 9 Explanation:
Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
Question 10 
Let L be a contextfree language and M a regular language. Then the language L ∩ M is
always regular  
never regular  
always a deterministic contextfree language  
always a contextfree language

Question 10 Explanation:
CFL is closed under regular intersection.
Question 11 
The language {a^{m} b^{n} C^{m+n}  m,n ≥ 1} is
regular
 
contextfree but not regular
 
context sensitive but not context free
 
type0 but not context sensitive

Question 11 Explanation:
Let us construct a PDA for the language
PUSH z_{0} into stack
PUSH K to stack of occurance of a
PUSH L to stack of occurance of b
POP K and L for the occurance of c
→ After POPno elements in the stack. So, this is context free language.
Note:
Regular:
R = {a^{n}  n ≥ 1}, Example.
CFL:
R = {a^{n}b^{m}  n,m ≥ 1}, Example.
PUSH z_{0} into stack
PUSH K to stack of occurance of a
PUSH L to stack of occurance of b
POP K and L for the occurance of c
→ After POPno elements in the stack. So, this is context free language.
Note:
Regular:
R = {a^{n}  n ≥ 1}, Example.
CFL:
R = {a^{n}b^{m}  n,m ≥ 1}, Example.
Question 12 
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
L is necessarily finite
 
L is regular but not necessarily finite
 
L is context free but not necessarily regular  
L is recursive but not necessarily context free 
Question 12 Explanation:
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicograhic order which is not accepted by TM.
The give 'L' is recursive but not necessarily context free.
The give 'L' is recursive but not necessarily context free.
Question 13 
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
Context free  
Regular  
Deterministic Context free  
Recursive 
Question 13 Explanation:
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
Question 14 
The C language is:
A context free language  
A context sensitive language  
A regular language  
Parsable fully only by a Turing machine 
Question 14 Explanation:
C and C++ are context sensitive languages.
Question 15 
L = 0^{+}  
L is regular but not 0^{+}  
L is context free but not regular  
L is not context free 
Question 15 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^{+}.
Question 16 
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 16 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.
Question 17 
Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
L = {xx has an equal number of a's and b's } is regular  
L = {a^{n}b^{n}n≥1} is regular  
L = {xx has more a's and b's} is regular  
L = {a^{m}b^{n}m ≥ 1, n ≥ 1} is regular 
Question 17 Explanation:
L = {a^{m}b^{n}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 18 
If L_{1} and L_{2} are context free languages and R a regular set, one of the languages
below is not necessarily a context free language. Which one?
L_{1}, L_{2}  
L_{1} ∩ L_{2}  
L_{1} ∩ R  
L_{1} ∪ L_{2} 
Question 18 Explanation:
Context free languages are not closed under intersection.
Question 19 
FORTRAN is a:
Regular language.  
Contextfree language.  
Contextsenstive language.  
None of the above. 
Question 19 Explanation:
Due to presence of some features FORTRAN cannot be handled by PDA.
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.
There are 19 questions to complete.