Identify-Class-Language

Question 1
 
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
       Theory-of-Computation       Identify-Class-Language       Gate 2011
Question 1 Explanation: 
L1: regular language
L2: context free language
L3: context sensitive language
Question 2
 
A
Not recursive
B
Regular
C
Context free but not regular
D
Recursively enumerable but not context free
       Theory-of-Computation       Identify-Class-Language       2009
Question 2 Explanation: 
The strings in L1 are { c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L2 are { ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L1 ∩ L2 is {axbx | x ≥0}, which is CFL but not regular.
Question 3
Which of the following is true for the language {ap|p is a prime} ?  
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
       Theory-of-Computation       Identify-Class-Language       Gate-2008
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
 
A
L1 is not a CFL but L2 is
B
L1 ∩ L2 = ∅ and L1 is non-regular
C
L1 ∪ L2 is not a CFL but L2 is
D
There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
       Theory-of-Computation       Identify-Class-Language       Gate 2008-IT
Question 4 Explanation: 
→ Both L1 and L2 are CFL. So option A is false.
→ L1 ∩ L2 = ∅, True and also L1 is non-regular. Option B is true.
→ L1 ∪ L2 is not a CFL but L2 is CFL is closed under union. So option C is false.
→ Both L1 and L2 accepted by DPDA.
Question 5
 
A
L2 and L3 only
B
L1 and L2 only
C
L3 only
D
L2 only
       Theory-of-Computation       Identify-Class-Language       Gate 2008-IT
Question 5 Explanation: 
L1 and L3 are regular.
L1 is limited to fixed range and L3 contains even number of 0's which is regular. No need to use more memory to implement L3.
Question 6
The language L = {0i21i | i≥0} over the alphabet {0,1, 2} is: 
A
not recursive.
B
is recursive and is a deterministic CFL.
C
is a regular language.
D
is not a deterministic CFL but a CFL.
       Theory-of-Computation       Identify-Class-Language       Gate-2007
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
 
A
G1 is context-free but not regular and G2 is regular
B
G2 is context-free but not regular and G1 is regular
C
Both G1 and G2 are regular
D
Both G1 and G2 are context-free but neither of them is regular
       Theory-of-Computation       Identify-Class-Language       Gate 2007-IT
Question 7 Explanation: 
Regular grammar is either right linear or left linear. A left linear grammar is one in which there is atmost 1 non-termial on the right side of any production, and it appears at the left most position.
Similarly, in right linear grammar, non-terminal appears at the right most position.
Here we can write a right linear grammar for G1 as
S → w(E
E → id)S
S → o
(w-while, o-other)
So, L(G1) is regular.
Now for G2 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 G1 and G2 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
 
A
L is recursively enumerable, but not recursive
B
L is recursive, but not context-free
C
L is context-free, but not regular
D
L is regular
       Theory-of-Computation       Identify-Class-Language       Gate-2006
Question 8 Explanation: 
Let L1 = {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)
L2 = {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 L1 and L2 have DFAs, hence they are regular. So the resulting Language.
L = L1 ∩ L2 (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
Question 9
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
A
L1 ∩ L2 is a deterministic CFL
B
L3 ∩ L1 is recursive
C
L1 ∪ L2 is context free
D
L1 ∩ L2 ∩ L3 is recursively enumerable
       Theory-of-Computation       Identify-Class-Language       Gate-2006
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 L1 ∩ L2 is a deterministic CFL.
Option B is false, as L3 is recursive enumerable but not recursive, so intersection with L1 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, L1 ∪ L2 is deterministic context free, hence it is also context free.
Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 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 context-free language and M a regular language. Then the language L ∩ M is
A
always regular
B
never regular
C
always a deterministic context-free language
D
always a context-free language
       Theory-of-Computation       Identify-Class-Language       Gate 2006-IT
Question 10 Explanation: 
CFL is closed under regular intersection.
Question 11
The language {am bn Cm+n | m,n ≥ 1} is
A
regular
B
context-free but not regular
C
context sensitive but not context free
D
type-0 but not context sensitive
       Theory-of-Computation       Identify-Class-Language       Gate-2004
Question 11 Explanation: 
Let us construct a PDA for the language
PUSH z0 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 = {an | n ≥ 1}, Example.
CFL:
R = {anbm | 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?  
A
L is necessarily finite
B
L is regular but not necessarily finite
C
L is context free but not necessarily regular
D
L is recursive but not necessarily context free
       Theory-of-Computation       Identify-Class-Language       Gate-2003
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.
Question 13
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
A
Context free
B
Regular
C
Deterministic Context free
D
Recursive
       Theory-of-Computation       Identify-Class-Language       Gate-2002
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
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
       Theory-of-Computation       Identify-Class-Language       Gate-2002
Question 14 Explanation: 
C and C++ are context sensitive languages.
Question 15
 
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-Computation       Identify-Class-Language       Gate-2000
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?  
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-Computation       Identify-Class-Language       Gate-1999
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.
Question 17
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-Computation       Identify-Class-Language       Gate-1996
Question 17 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 18
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-Computation       Identify-Class-Language       Gate-1996
Question 18 Explanation: 
Context free languages are not closed under intersection.
Question 19
FORTRAN is a:
A
Regular language.
B
Context-free language.
C
Context-senstive language.
D
None of the above.
       Theory-of-Computation       Identify-Class-Language       GATE-1987
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.
There are 19 questions to complete.