TheoryofComputation
Question 1 
ab  
ba  
ac  
as 
Question 2 
A = {a^{n} b^{n}  n = 1, 2, 3, …. } is a regular language  
The set B, consisting of all strings made up of only a’s and b’s having an equal number of a’s and b’s defines a regular language  
L(A * B) ∩ B gives the set A  
None of the above 
Option B: False: Equal number of a's and equal number of b's is also DCFL but not regular
Option C: False: L(A*B) ∩ B gives the set B but not set A.
L(A*B)= {AB+ AAB + …+AAAAB+B}
L(A*B)∩B=B
Question 3 
Union  
Complementation  
Kleene star  
Product 
Question 4 
Complements a given bit pattern  
Finds 2’s complement of a given bit pattern  
Increments a given bit pattern by 1  
Changes the sign bit 
Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111

1000 = I/p

It results 2's complement.
Question 5 
2x – 1  
2x  
2x + 1  
2^{x} 
→ For CNF, it is 2x  1
→ For GNF, it is x
Question 6 
S1 : Every contextsensitive language L is recursive
S2 : There exists a recursive language that is not contextsensitive
Which statements are true?
Only S1 is correct  
Only S2 is correct  
Both S1 and S2 are not correct  
Both S1 and S2 are correct 
Question 7 
There is a unique minimal DFA for every regular language  
Every NFA can be converted to an equivalent PDA  
The complement of every contextfree language is recursive  
Every nondeterministic PDA can be converted to an equivalent deterministic PDA 
1. DPDA accept only a proper subset of CFL's ie. LL grammars.
2. NPDA can accept any CFL, which makes them more powerful over DPDA
3. Every NPDA can not be converted to an equivalent DPDA
Question 8 
(L + D)*  
(L.D)*  
L(L + D)*  
L(L.D)* 
Question 9 
Kleene Star L * of L  
Intersection L ∩ P  
Union L ∪ P  
Set Difference 
→ Set Difference A – B can be written as A ∩ B’ where B’ denotes complementation of B. So we can say that Recursively Enumerable problems are not closed under Set Difference
Question 10 
S → ABCc ∣ bc
BA → AB
Bb → bb
Ab → ab
Aa → aa
Which of the following sentences can be derived by this grammar?
abc  
aab  
abcc  
abbc 
S→ABc
Now see each of remaining production
Bb→bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
So
S→ABc→abc
Question 11 
Set of strings with 2 a’s and 2 b’s  
Set of strings with 2 a’s 2 b’s followed by b  
Set of strings with 2 a’s followed by b’s which is a multiple of 3  
Set of strings with even number of a’s followed by odd number of b’s 
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
Question 12 
not contextfree, not linear  
not contextfree, linear  
contextfree, not linear  
contextfree, linear 
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of nonterminals
It is clearly seen that given grammar is not linear but contextfree.
Question 13 
S > AB
A > aAbϵ
B > bB b
{a^{m}b^{n}  n>=m, m>0}  
{a^{m}b^{n}  n>=m, m>=0}  
{a^{m}b^{n}  n>m, m>0}  
{a^{m}b^{n}  n>m, m>=0} 
Hence it is a^{m}b^{n}  n>m, m>=0
Question 14 
L_{1} ∩ L_{2} is contextfree  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is contextfree  
L_{1} ∩ L_{2} ∩ L_{3} is recursively 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 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, 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 15 
Then which of the following is true?
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 
L can only be accepted by a Turing machine
Question 16 
without rewinding capability and unidirectional tape movement  
rewinding capability and unidirectional tape movement  
without rewinding capability and bidirectional tape movement  
rewinding capability and bidirectional tape movement 
→ The finite state machine has less computational power than some other models of computation such as the Turing machine.
→ The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM's memory is limited by the number of states it has.
→ A finite state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite state machine is accepted by such a kind of restricted Turing machine, and vice versa.
Question 17 
(0*10*1)*  
0*(10*10*)*  
0*(10*1*)*0*  
0*1(10*1)10* 
→ We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (Regular expression: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (Regular expression: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (Regular expression: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Question 18 
G = {S→ SS, S→ ab, S→ ba, S→ ^}
I. G is ambiguous
II. G produces all strings with an equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about?
I only  
I and III only  
II and III only  
I, II and III 
G doesn’t produce all strings of an equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
Question 19 
Regular  
Contextfree  
Context Sensitive  
Recursive 
→ If L’ are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of L’ Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L.
→ This implies that L must be recursive.
Question 20 
all palindromes  
all odd length palindromes  
strings that begin and end with the same symbol  
all even length palindromes 
Question 21 
S → Aa
A → Ba
B → abc
Type 0  
Type 1  
Type 2  
Type 3 
Question 22 
Unified problem  
Boolean function  
Recursive problem  
Decidable 
Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise.
Recursive languages are also called decidable.
Question 23 
Which of the following sentences can be generated by
S > aS  bA
A > d  cA
bccdd  
abbcca  
abcabc  
abcd 
S > aS  bA
A > d  cA
From the given productions, it is not possible to derive the sentence bccdd(two consecutive d’s).So option A is not correct.
In the string “abbcca”, there are two consecutive c’s followed by the letter ‘a’, This can’t be derived from the given productions,
From the given productions, it is also not possible to derive string which consists of the letter ‘c’ followed by ‘a’ , So the option (c ) also not correct
From given productions, we can generate the string “abcd”
Question 24 
q_{0}, q_{1}, q_{2}  
[q_{0}, q_{1}], [q_{0}, q_{2}], [ ]  
q_{0}, [q_{1}, q_{2}]  
[q_{0}, q_{1}], q_{2} 
→From the diagram, initially “q2” is final state.
→As there is epsilon transitions from qo to q1 and q1 to q2 and finally we reach the end state so q0,q1 are part of final states then q0,q1 and q2 are final states.
Question 25 
m x 2^{n}  
2^{m+n}  
2^{mn}  
m+n 
Generally FSM consists of 2^{x} states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2^{mn}.
Question 26 
S → SS
S → (S)
S → ε
10  
15  
12  
16 
To generate the string ((() ()) ()) , we need to perform the steps sequentially.
As the string starts with left parentheses, we will start with the production S → (S).
Depending upon the string we will go for either left or right tree generation.
1) S → (S) // Replacing S by (S)
2) S → (SS) // Replacing by S by SS
3) S → ((S)S) //Replacing S by(S)
4) S → ((SS)S)// Replacing S by SS
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S)) [S → ε]
8) S → ((()(S))S) [S → ε]
9) S → ((()())S) [S → ε]
10) S → ((()()))
Question 27 
7  
9  
10  
11 
String which consists of 0’s and 1’s
Language is number of 0’s is divisible by 2 and number of 1’s is divisible by 5
Machine is minimum state deterministic finite automaton
The set of strings generated by {0,1} are ={ε,0,1,00,11,01,10,000,011,010 .. and so on}
The strings which are generated by language which is specified in the questions are
{ ε , 00, 11111, 0011111, 0011111 , 1111100, 1010111 , 000011111,….and so on }
So, strings accepted by the automaton have to be of length 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12….and so on, i.e. equation for length will be 2x + 5y (where x,y>=0 )
Number of 0’s divisible by 2 means , the possible remainders are 0 and 1 i.e; 2
Number of 1’s divisible by 5 means , the possible remainders are 4,3,2,1,0 i.e; 5
Total number of states are 2*5 =10
Question 28 
{1, 0}* {01}  
{1, 0}* {1}  
{1}{1, 0}* {1}  
1*0* {0, 1} 
Question 29 
Let denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in that are accepted by M is
0  
1  
2  
3 
01110110
01110111
Above two strings are are having constraint that 2nd, 3rd, 6th and 7th bits are 1. So, it satisfied above condition.
Question 30 
S → AB
A → a
A → BaB
B → bbA
Which of the following statements is FALSE?
The length of every string produced by this grammar is even  
No string produced by this grammar has three consecutive a’s  
The length of substring produced by B is always odd  
No string produced by this grammar has four consecutive b’s 
Question 31 
it may halt and accept the input  
it may halt by changing the input  
it may halt and reject the input  
it may never halt 
→ Halting of Turing machine is an undecidable problem. A general algorithm to solve the halting problem for all possible programinput pairs cannot exist.
→ Possible outcomes are
1. It may halt and accept the input.
2. It may halt and reject the input.
3. It may never halt.
Question 32 
Two finite state machines are said to be equivalent if they :
Have the same number of edges  
Have the same number of states
 
Recognize the same set of tokens
 
Have the same number of states and edges

Question 33 
The finite state machine given in figure below recognizes :
any string of odd number of a’s
 
any string of odd number of b’s
 
any string of even number of a’s and odd number of b’s  
any string of odd number of a’s and odd number of b’s

L = {ab, ba, ababab, bababa, ..........}
Here, L is the language containing odd number of a’s and odd number of b’s.
Question 34 
A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :
0  
1  
1 or more  
2 or more

→ So, total of 2 or more auxiliary memory are needed to make a pushdown automata behaves like a Turing machine.
Question 35 
Pushdown automata can recognize language generated by
Only context free grammar  
Only regular grammar  
Context free grammar or regular grammar  
Only context sensitive grammar

B ➝ aBb  ab ; Here B is a Context free grammar which can be accepted by the pushdown automata.
Question 36 
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :
2n−1  
2n  
n+1  
n^{2}

Example:
Derive string “ab” from above grammar.
Sol:
Using formula 2n  1; where n = length of string
2(2)  1 = 3
Hence, the answer is option(1).
Question 37 
Consider the following two Grammars :
 G1 : S → SbSa
G2 : S → aBab, A → GABa, B → ABbb
Which of the following option is correct ?
Only G1 is ambiguous  
Only G2 is ambiguous  
Both G1 and G2 are ambiguous  
Both G1 and G2 are not ambiguous

To generate string “ababa” using G1 grammar the two different parse tree possible are:
Question 38 
Context sensitive language can be recognized by a :
Finite state machine  
Deterministic finite automata
 
Nondeterministic finite automata
 
Linear bounded automata

L = {a^{n}b^{n}c^{n} where n>0}
is a context sensitive language and cannot be recognized by Finite state machine, Deterministic finite automata, Nondeterministic finite automata but L can be recognized by Linear Bounded Automata.
So, Context Sensitive Language can be recognized by Linear Bounded Automata.
Question 39 
The set A = { 0^{n} 1^{n} 2^{n}  n=1, 2, 3, ......... } is an example of a grammar that is :
Context sensitive  
Context free  
Regular
 
None of the above

→ In case of Context Free grammar we have a stack only in which we can push 0’s as they come as input and can POP 0’s as 1’s come as input but when 2’s comes as input string we have NULL at the top of the stack so this Grammar can’t be a context free grammar.
→ Since in case of Context sensitive grammar we have linear bounded automata and a read/write head which can move backward and upward so this grammar can be accepted by Linear Bounded Automata. So, this grammar is a Context Sensitive Grammar.
Question 40 
Consider the following statements( ) :

S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct ?
Both S1 and S2 are correct  
Both S1 and S2 are not correct  
Only S1 is correct
 
Only S2 is correct

→ Halting problem of a turing machine is undecidable because if a turing machine accepts a string then it will halt but if a turing machine does not accept a string then it may or may not halt(can enter infinite loop). So, statement S2 is also correct.
Question 41 
ab*b*  
a*b*  
b*b  
b*ab* 
Step1: Starting state has loop with symbol ‘b’ . It means, we can get n number of times ‘b’.
Step2: The symbol ‘a’ between the starting state and end state. It means we can get only one
‘a’ after b*.
Step3: The final state also having self loop with symbol ‘b’.
Question 42 
The set of all strings containing the substrings 11  
The set of all string containing at most two 1’s  
The set of all strings containing at least two 1’s  
The set of all strings that begins and ends with only 0. 
1→ definitely one should be there.
(0+1)* → We can take zero or many times
1→ definitely one should be there.
So, this regular expression containing at least two 1’s.
Question 43 
Regular  
Context free but non regular  
Context sensitive but non context free  
Type 0 but non context sensitive 
Question 44 
(1) A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language
(2) The complement of a recursive language is recursive
(3) The complement of a context free language is context free
Only (1)  
(1) and (2)  
(1),(2) and (3)  
(2) and (3) 
TRUE: The complement of a recursive language is recursive
FALSE because The complement of a deterministic context free language is deterministic context free.
Question 45 
(1) baaaba
(2) aabaaaa
(3) baaabaaaabaa
(4) baaabaaa
(1)  
(2)  
(3)  
(4) 
L = { ab, aa, baa }
Let S1 = ab , S2 = aa and S3 =baa
Option1: baa ab a , We can’t partition with combinations of S1,S2 and S3.
Option2: aa baa aa, We can’t partition with combinations of S1,S2 and S3.
Option3: baa ab aa aa baa, We can partition this into S3S1S2S2S3
Option4: baa ab aa a, We can’t partition with combinations of S1,S2 and S3.
We can’t partition the above options with combinations of {ab, aa, baa} except Option3.
So the L* Consists of the string “baaabaaaabaa:
Question 46 
finite state automaton  
2way linear bounded automata  
pushdown automata  
Both (B) and (C) 
Question 47 
Decidable  
Undecidable  
interpretive  
nondeterministic 
● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.
● For simple machine models, such as finite automata or pushdown automata, many decision problems are solvable. In the case of deterministic finite automata, problems like equivalence can be solved even in polynomial time
Question 48 
{a,b,ab,aa}  
{a,b,ba,bb}  
{a,b}  
{aa,ab,ba,bb} 
● (ab) means either a or b.
● The expression consists of two symbols of (ab),which strings starting with either a or b and ending with either a or b.
Question 49 
have same number of states  
have same number of edges  
have same number of states and edges  
recognized same set of tokens 
Question 50 
Consider the following two languages:
 L_{1} = {x  for some y with y=2^{x}, xy ∈ L and L is regular language}
L_{2} = { x  for some y such that x = y, xy∈L and L is regular language}
Which one of the following is correct?
Both L_{1} and L_{2} are regular languages
 
Both L_{1} and L_{2} are not regular languages
 
Only L_{1} is regular language  
Only L_{2} is regular language

Consider a language L= {a^{3n}  n ≥ 0} , the strings in L are {ϵ, aaa, aaaaaa, …….}
then L_{1} = {a^{n}  n ≥ 0} as every string in L can be broken into three equal parts.
DFA for L:
DFA for L_{1}:
By same logic L_{2} is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L_{1}, since we can break only even length string into two equal parts such that x = y if “xy ∈ L”.
Question 51 
Consider the following language:
 L_{1} = { a^{n+m} b^{n}a^{m } n,m ≥ 0}
L_{2} = { a^{n+m }b^{n+m} a^{n+m} n,m ≥ 0}
Which one of the following is correct?
Code:Only L_{1} is Context Free Language
 
Both L_{1} and L_{2} are not Context Free Language
 
Only L_{1} is Context Free Language  
Both L_{1} and L_{2} are Context Free Language

Since we can have a pushdown automata for L_{1} so we can say L_{1} is a CFL.
→ L_{2} is not a context free language because L is equivalent to language = {a^{p}b^{p}a^{p}  p ≥ 0}.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L_{2}.
L_{2} is not a CFL.
Question 52 
Consider the following problems:
 (i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?
Code:Only (ii) and (iii) are undecidable problems
 
(i), (ii) and (iii) are undecidable problems  
Only (i) and (ii) are undecidable problems
 
Only (i) and (iii) are undecidable problems

• Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable.
Question 53 
Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.
 Consider the following:
(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)
Choose the correct answer from the code given below :
Code :Only (i) is correct  
Both (i) and (ii) are correct
 
Only (ii) is correct
 
Neither (i) nor (ii) is correct

L(r) = { ab, aab, aaab, aaaab, ………… }
L(t) = { b, ab, aab, aaab, aaaab, ……… }
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible string over a, b.
So L(s) ⊆ L(r) and L(t) ⊆ L(r).
L(r) can’t generate “b” but L(t) can’t.
So L(s) ⊆ L(t).
Question 54 
Consider the language L given by
L = {2^{nk}  k>0, and n is nonnegative integer number}
The minimum number of states of finite automaton which accept the language L is
n  
n+1  
2^{n}  
n(n+1)/2 
assume n = 2 (for instance)
then we have : L = a^{2k}  k>0
so k's value will be {1, 2, 3, 4, ........} and accordingly in L we have strings {a^{2}, a^{4}, a^{6}, a^{8} .......}
→ It is clearly even number of a's (except zero a's) and for this we have 3 state DFA,
→ If n=3 then we will have a^{3}, a^{6}, a^{9} ..........
→ So, we require 4 states DFA
Hence answer will be "n+1" states are required.
Question 55 
Which of the following problem is decidable for recursive language (L) ?
Is L = ф ?  
Is w∈L, where w is a string ?
 
Is L = R, where R is given regular set ?
 
Is L = Σ* ? 
→ Every decidable language is TuringAcceptable.
→ For recursive language membership problem is decidable, i.e., a string “w” belongs to a recursive language “L” is decidable. Rest all are undecidable.
→ If language is recursive then it means , we have a Turing machine for the language which always halt. So when a string “w” is given to this turing machine it always halt either by accepting “w” or by rejecting “w”. Hence “Is w∈L” is decidable.
Question 56 
Consider R to be any regular language and L_{1}.L_{2} be any two contextfree languages
Which one of the following is correct ?
Option 2: L_{1} is a CFL and R is a Regular language and if we do L_{1}  R the result will Regular language.
L_{1} = {a^{n} b^{n}  n>0} is a context free language which can generate strings {ab, aabb, aaabbb, …….}
R = (a+b)* which can generate language {∈, a, b, aa, bb, ab, ba, …….}
So, L_{1}  R = {ф} which is a regular language.
And since every regular language is also a CFL so option 2 is correct.
Option 3: Context free languages are not closed under complementation. So option 3 is incorrect.
Option 4: Context free languages are not closed under Intersection. So option 4 is incorrect.
Question 57 
1.∅
2.{∈}
3.a*
4.{a, ∈}
1  
2  
3  
4 
Hence the complement of language is: {a* − a+} = {ϵ}
Question 58 
Neither L nor L' is RE  
One of L and L' is RE but not recursive;The other is not RE  
Both L and L' are RE but not recursive  
Both L and L' are recursive 
Question 59 
L1′ is recursive and L2′ is recursively enumerable  
L1′ is recursive and L2′ is not recursively enumerable  
L1′ and L2′ are recursively enumerable  
L1′ is recursively enumerable and L2′ is recursive 
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
Question 60 
 Does a given ever produce an output?
 If L is a context free language, then is L’ (complement of L) also context free?
 If L is a regular language, then is L’ also regular?
 If L is a recursive language, then is L’ also recursive?
(a), (b), (c), (d)  
(a), (b)  
(b), (c), (d)  
(c), (d) 
→ Context free languages are not closed under complement operation, so complement of CFL may or may not be CFL. Hence statement 2 is also undecidable.
→ Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its nonfinal states and viceversa. Hence it is decidable and if L is a regular language, then, L must also be regular.
→ Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
Question 61 
If a language is context free it can always be accepted by a deterministic pushdown automaton  
The union of two context free language is context free  
The intersection of two context free language is context free  
The complement of a context free language is context free 
Question 62 
Languages for palindrome and prime  
Languages for palindrome and EvenEven  
Language for prime and EvenEven  
Language for palindrome and factorial 
To show that L is not regular we need to do the following:
Question 63 
Finite automata  
Pushdown automata  
Non deterministic turing machine  
Non deterministic PDA 
Question 64 
Given problems is computable  
Given problem is non computable  
Given problem has finite state solution  
Given problem is solved in polynomial time. 
Question 65 
a*b*  
(a  b)*  
(ab) *  
(a  b*) 
Question 66 
Non deterministic finitestate automata are equivalent to deterministic finitestate automata  
Non deterministic PDA are equivalent to Deterministic PDA  
Nondeterministic turing machines are equivalent to deterministic PDA  
Multi tape Turing machines are equivalent to single tape Turing machines 
→ NFA and DFA having same power.
→ NTM and DTM having same power.
→ Multi tape Turing machines are equivalent to single tape Turing machines
Question 67 
L1.L2  
L1 ∩ L2  
L1 ∩ R  
L1 U L2 
→ L1 ∩ R is closed under CFL
→ L1.L2 and L1 U L2 is closed under CFL
Question 68 
(a+b)  
(a+b)(a+b)*  
(a+b)(a+b)  
all of these 
● The option C gives aa,ab,ba or bb which are of length of 2
● But the CFG will produce strings, which of length of greater than 2 also.
● The option B gives string starts with either a or b followed by any number of a’s or b’s which is equivalent to CFG.
Question 69 
regular language  
context free language  
context sensitive language  
recursive enumeration language 
Question 70 
A={a^{n}b^{n} n= 0,1,2,3..} is regular language  
Set B of all strings of equal number of a's and b's defines a regular language  
L(A*B*) ∩ B gives the set A  
None of these 
OptionB, equal no of a's and equal no of b's is belongs to deterministic context free languages but not regular
OptionC is TRUE. If they given
L(A*B) ∩ B gives the set B but not set A.
L(A*B)= {AB+ AAB + …+AAAAB+B}
L(A*B)∩B=B
Question 71 
Union  
Concatenation  
Kleene's closure  
All of these 
Question 72 
No  
Yes  
Sometimes  
Depends on NFA 
Question 73 
L _{1} = {x  for some y with  y = 2 ^{x} ,xy∈ L and L is regular language}
L _{2} = { x  for some y such that x = y, xy∈ L and L is regular language}
Which one of the following is correct?
Both L _{1} and L_{ 2} are regular languages  
Both L _{1} and L _{ 2} are not regular languages  
Only L _{1} is regular language  
Only L _{ 2} is regular language 
Consider a language L= {a 3n  n ≥ 0} , the strings in L are {ε, aaa, aaaaaa, .......}
then L _{1} = {a^{ n}  n ≥ 0} as every string in L can be broken into three equal parts .
DFA for L
DFA for L _{1}
By same logic L _{2} is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L_{ 1} , since we can break only even length string into two equal parts such that x = y if “xy ε L”
Question 74 
10  
45  
56  
55 
n*(n+1)/2 + 1
We have added 1 because it may include a NULL string also.
The number of substrings = 10*(11)/2 +1
The number of substrings = 56
Question 75 
L _{1} = { a^{ n+m} b^{ n} a^{ m}  n, m ≥ 0 }
L _{2} = { a^{ n+m} b^{ n+m} a^{ n+m} n, m ≥ 0 }
Which one of the following is correct?
Only L_{ 1} is Context Free Language  
Both L _{1} and L_{ 2} are not Context Free Language  
Only L _{1} is Context Free Language  
Both L_{ 1} and L_{ 2} are Context Free Language 
Since we can have a pushdown automata for L _{1} so we can say L _{1} is a CFL.
→ L _{2} is not a context free language because L is equivalent to language= {a ^{p} b^{ p} a^{ p}  p ≥ 0 }.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L_{ 2} .
L _{2} is not a CFL.
Question 76 
(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?
Only (ii) and (iii) are undecidable problems  
(i), (ii) and (iii) are undecidable problems  
Only (i) and (ii) are undecidable problems  
Only (i) and (iii) are undecidable problems 
● Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable
Question 77 
(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)
Only (i) is correct  
Both (i) and (ii) are correct  
Only (ii) is correct  
Neither (i) nor (ii) is correct 
L(r) = { ab, aab, aaab, aaaab, ............}
L(t) = { b, ab, aab, aaab, aaaab, .........}
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible
string over a, b. So L(s)⊆L(r) and L(t)⊆L(r)
L(r) can’t generate “b” but L(t) can’t. So L(s)⊆L(t).
Question 78 
L = { 2 _{nk}  k > 0 , and n is non − n egative integer number }
The minimum number of states of finite automaton which accept the language L is
n  
n+1  
2 ^{n}  
n (n + 1 )/2 
assume n= 2 (for instance)
then we have : L= a ^{2k}  k>0
so k's value will be {1,2,3,4,........} and accordingly in L we have strings {a ^{2} ,a^{ 4} ,a^{ 6} , a^{ 8} .......}
→ It is clearly even number of a's (except zero a's) and for this we have 3 state DFA,
→ If n=3 then we will have a ^{3} , a^{ 6} , a^{ 9} ..........
→ So, we require 4 state DFA
hence answer will be "n+1" states are required.
Question 79 
Is L = ф ?  
Is w∈L, where w is a string ?  
Is L=R, where R is given regular set ?  
Is L = Σ* ? 
→ Every decidable language is TuringAcceptable.
→ For recursive language membership problem is decidable, i.e., a string “w” belongs to a recursive language “L” is decidable. Rest all are undecidable.
→ If language is recursive then it means , we have a Turing machine for the language which always halt. So when a string “w” is given to this turing machine it always halt either by accepting “w” or by rejecting “w”. Hence “Is w∈L” is decidable.
Question 80 
(L _{1} ⋃ L_{ 2} ) − R is context free  
L _{1} − R is context free  
L _{1} is context free  
L _{1} ⋂ L_{ 2} is context free 
Option 2: L _{1} is a CFL and R is a Regular language and if we do L _{1}  R the result will Regular language.
L _{1} = {a n b n  n>0} is a context free language which can generate strings {ab, aabb, aaabbb, .......}
R = (a+b)* which can generate language {∈, a, b, aa, bb, ab, ba, .......}
So L _{1} R = {ф} which is a regular language.
And since every regular language is also a CFL so option 2 is correct.
Option 3: context free languages are not closed under complementation. So option 3 is incorrect.
Option 4: context free languages are not closed under Intersection. So option 4 is incorrect.
Question 81 
FSA cannot remember arbitrarily large amount of information  
FSA cannot deterministically fix the midpoint  
Even if the midPoint is known an FSA cannot find whether the second half of the matches the first half  
All of the above 
Question 82 
L1L2 is not context free  
L1 intersection L2 is context free  
~L1 is context free  
Both (A) and (C) 
Question 83 
Turing machine is a simple mathematical model of general purpose computer  
Turing machine is more powerful than finite automata  
Turing Machine can be simulated by a general purpose computer  
All of these 
● Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
● The machine operates on an infinite memory tape divided into discrete cells.
● The machine positions its head over a cell and "reads" (scans)the symbol there.
● Then, as per the symbol and its present place in a finite table of userspecified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allowing symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.
Question 84 
M1 and M2 has the same number of states  
M1 and M2 accepts the same language i.e L(M1)=L(M2)  
M1 and M2 has the same number of final states  
None of the above 
Two DFAs M1 and M2 over the same alphabet are equivalent if they accept the same language:
L(M1 ) = L(M2 )
Question 85 
Strings not starting with 11  
Strings of odd length  
Strings starting with 00  
Strings of even length 
We can’t generate strings with only 00, we can generate strings starting with 00, 01 and 10 also, So option C is incorrect.
From the given expression (00+01+10)(0+1)*, we can’t generate strings with 11 , we can generate strings starting with 00, 01 and 10.
Question 86 
R1 ∩ R2 is not regular  
R1 ∪ R2 is not regular  
Σ * – R1 is regular  
R1 * is not regular 
1) Intersection
2) Union
3) Complement
4) Kleeneclosure
Σ*  R_{1} is the complement of R_{1}.
Question 87 
State whether TRUE or FALSE
 (i) In NDFA, the transition function δ: Q × Σ → 2^{Q}
(ii) NDFA does not permit empty string transitions
(i) False (ii) False
 
(i) True (ii) False
 
(i) False (ii) True
 
(i) True (ii) True 
An NDFA can be represented by a 5tuple (Q, ∑, δ, q_{0}, F) where
Q is a finite set of states.
∑ is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2^{Q}
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
q_{0} is the initial state from where any input is processed (q_{0} ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
DFA: Empty string transitions are not seen in DFA.
NDFA: permits empty string transitions.
Question 88 
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string)
 
It is the finite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string)
 
It is the finite set of all possible strings of all possible lengths over Σ(input set)
 
It is the infinite set of all possible strings of all possible lengths over Σ(input set) 
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
Question 89 
A language is a subset of Σ* for some alphabet Σ. If a language takes all possible strings of length 2 over Σ = {a,b}, then, which of the below is correct?
L = {ab,bb,ba}
 
L = {aa,ab,ba,bb}
 
L = {ab,bb,aa}
 
L = {ab,ba,aa} 
→ We are computing all possible strings using 2^{n} formula. Where n is number of strings.
Question 90 
A DFA can be expressed as a 5 tuple(Q, Σ, δ, q_{0}, F), where δ is the transition function defined as ___?
δ: Σ → Q
 
δ: Q x Q → Σ  
δ: Q → Q
 
δ: Q x Σ → Q

DFA consists of 5 tuples {Q, ∑, q, F, δ}.
Q : set of all states.
∑ : set of input symbols. (Symbols which machine takes as input)
q : Initial state. (Starting state of a machine)
F : set of final state.
δ : Transition Function, defined as δ: QX∑ → Q.
Question 91 
If r and s are regular expression representing the languages L(r) and L(s), respectively, then which of the following is FALSE?
(r)(s) is a regular expression representing L(r)UL(s)
 
(r)(s) is a regular expression representing (L(r))* or (L(s))*  
(r)* is a regular expression representing (L(r))*  
(r)(s) is regular expression representing L(r)L(s)

1. Union : (r)(s) is a regular expression denoting L(r) U L(s)
2. Concatenation : (r)(s) is a regular expression denoting L(r)L(s)
3. Kleene closure : (r)* is a regular expression denoting (L(r))*
(r) is a regular expression denoting L(r).
Question 92 
L={ x^{n} y^{n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x ^{+} y ^{+}
i only  
i and ii only  
ii and iii only  
ii only 
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1:E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X ^{+} means one or more x’s
Y ^{+} means one or more y’s
Definition 2 :
The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x^{ +} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Question 93 
(0+1+0+1+0+1+0+1)^{4}  
(0+1)^{4}  
(01)^{4}  
(0+1+ɛ)^{4} 
Question 94 
Any derivation of W_{1} has exactly the same number of steps as any derivation of W_{2}  
Different derivation have different length  
Some derivation of W_{1} may be shorter the derivation of W_{2}  
None of the options 
W_{1} and W_{2} are 2 strings,
W_{1}=W_{2} means same length
Example CFG grammar:
S→ Cbb  cc
C→ a
W_{1}=cc W_{2}=Cbb
As per the grammar, W_{1} require only one derivation S→ cc
W_{2} requires two derivations S→ Cbb→ abb
It means W_{1} is smaller than W_{2}.
Question 95 
Set of strings with either a or one or more occurences of b followed by c.  
(b*c+a)  
Set of strings with either a or zero or more occurence of b followed by c  
Both (B) and (C) 
Question 96 
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not
P4: For any given CFG G, to determine whether ɛ belongs to L(G)
P2 only  
P1 and P2 only  
P2 and P3 only  
P3 only 
A problem is decidable if we can construct a Turing machine which will halt in finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable problem has an algorithm to determine the answer for a given input.
Examples
Equivalence of two regular languages:Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.
Finiteness of regular language: Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.
Emptiness of context free language: Given a context free language, there is an algorithm whether CFL is empty or not.
Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.
Examples
Ambiguity of contextfree languages: Given a contextfree language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.
Equivalence of two contextfree languages: Given two contextfree languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.
Everything or completeness of CFG: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.
Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.
Question 97 
Set difference  
Complement  
Both (A) and (B)  
None of the options 
→ The set difference LP may or may not be recursively enumerable.
→ If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.
Question 98 
Any string containing '1' as substring
 
Any string containing '01' as substring  
Any string containing '011' as substring  
All string containing '001' as substring 
Question 99 
Unambiguous CFG  
Ambiguous CFG  
Not a CFG  
Deterministic CFG 
Question 100 
Regular  
Context free but not regular  
Recursive but not necessarily context free  
Recursively enumerable but not necessarily recursive 
Question 101 
i.Union
ii.Intersection
iii.complement
iv.Concatenation
v.star closure
i only  
Both i,iv  
i,ii,iv and v  
All of the options 
1)Union
2)Intersection
3)Concatenation
4)Star closure
Question 102 
r1*r2*  
(r1r2)*  
r1*r2*+r1r2  
(r1*r2*)* 
→ Given in regular expression to get together also many number of occurrences. So, correct answer is option D.
Question 103 
S1: The power of a multi tape Turing machine is greater than the power of a single tape turing machine
S2: Every non deterministic Turing machine has an equivalent deterministic Turing machine
S1  
S2  
Both S1 and S2  
None of the options 
S2:NonDeterministic TM is equivalent to DTM
Question 104 
mealy and moore machine are language acceptors  
Finite state automata is language translator  
NPDA is more powerful than DPDA  
mealy machine is more powerful than moore machine 
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
Question 105 
(00+(11)*0)  
1(0+1)*101  
(10)*(01)*(00+11)*  
110*(0+1) 
Question 106 
n(n+1)  
n^{2} +1  
n^{2} 1  
n(n+1)/2 
→ There are total n(n+1)/2 table entries, the whole table construction process takes O(n^{3}) time in worst case.
Question 107 
Deterministic Context free language are closed under complement  
Deterministic Context free language are not closed under union  
Deterministic Context free language are closed under intersection with regular set  
All of the options 
→ Deterministic Context free language are not closed under union
→ Deterministic Context free language are closed under intersection with regular set
Question 108 
PDA  
TM  
LBA  
None of the options 
1)DPDA accept only a proper subset of CFL's ie. LL grammars.
2)NPDA can accept any CFL, which makes them more powerful over DPDA
→ Deterministic TM is equal power to Non deterministic TM
Question 109 
L1: Set of languages accepted by NFA
L2: Set of languages accepted by DFA
L3: Set of languages accepted by DPDA
L4: Set of languages accepted by NPDA
L5: Set of recursive languages
L6. Set of recursively enumerable languages?
L1,L2⊂ L3⊂ L4⊂ L5⊂ L6  
L1⊂L2⊂ L3 ⊂L4⊂ L5 ⊂L6  
L2⊂L1⊂ L3 ⊂L4⊂ L5⊂ L6  
L1⊂L2⊂ L3⊂ L4⊂ L6⊂ L5 
Question 110 
Pushdown automata  
Turing machine  
Linear Bounded Automata  
None of the options 
→ NPDA is more powerful than DPDA.
Question 111 
i.((01)*(10)*)*
ii.(10+01)*
iii.(01)*+(11)*
iv.(0*+(11)*+0*)*
i and ii  
ii and iii  
iii and iv  
iv and i 
{ε,01,10,0110,0101,1010,010110,01011010, ……}
→ The set of strings generated by the expression (10+01)* are
{ε,10,01,1010,0101,0110,101010,010101….}
→ The set of strings generated by the expression (01)*+(11)* are
{ε,01,11,0101,1111,010101,111111…}
→ The set of strings generated by the expression (0*+(11)*+0*)*are
{ε,0,11,00,000,011,110,0110,00110,01100,.....}
Compare the strings which are generated by option1 and option2.
Question 112 
NFA
 
DFA  
NFAɛ / NFAl
 
All of the above 
We extend the class of NFAs by allowing instantaneous (ε) transitions:
1. The automaton may be allowed to change its state without reading the input symbol.
2. In diagrams, such transitions are depicted by labeling the appropriate arcs with ε.
3. Note that this does not mean that ε has become an input symbol. On the contrary, we assume that the symbol ε does not belong to any alphabet.
Question 113 
making starting state as final state  
make final as a starting state  
make final states nonfinal and non final as final  
None of the options 
Question 114 
Union  
Dot  
Kleene  
none of the options 
→ If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.
Question 115 
mealy and moore machine are language acceptors  
Finite state automata is language translator  
NPDA is more powerful than DPDA  
mealy machine is more powerful than moore machine 
1.DPDA accept only a proper subset of CFL's ie. LL grammars.
2.NPDA can accept any CFL, which makes them more powerful over DPDA
Question 116 
Regular  
Non regular  
Recursive  
Non Recursive 
Example
L1= {a^{m} b^{n } n ≥ 0 and m ≥ 0} and L2= {a^{m} b^{n} ∪ b^{n} a^{m}  n ≥ 0 and m ≥ 0}
L3 = L1 ∩ L2 = {a^{m} b^{n}  n ≥ 0 and m ≥ 0} is also regular.
Question 117 
Q*P  
QP*  
Q*P*  
(P*Q*)* 
→ In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the properties of regular expressions.
Statement:
Let P and Q be two regular expressions.
If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*
Proof:
R=Q+(Q+RP)P [After putting the value R=Q+RP]
=Q+QP+RPP
When we put the value of R recursively again and again, we get the following equation:
R=Q+QP+QP^{2}+QP^{3}…..
R=Q(ε+P+P^{2}+P^{3}+…. )
R=QP*[As P* represents (ε+P+P2+P3+….)]
Question 118 
Type 0  
Type 1
 
Type 2  
Type 3 
Question 119 
{0,1,01,ɛ}  
{0,1,ɛ}  
{0,1,01,11,00,10,ɛ}  
{0,1} 
Question 120 
DFA>NFA  
NFA>DFA
 
Equals  
Can't be said 
Question 121 
16  
26  
32  
64 
=2^{2}*2^{4}
=4*16
=64
Question 122 
π  
∅  
a  
b 
Question 123 
1  
0  
2  
none of the options 
Question 124 
(0+0+1)(0+0+1)  
(0+0+0)(0+1+1)  
(1+0+0)(1+1+1)  
(0+1+0)(1+0+1) 
→ (0+0+0) gives the value 0
→ (0+1+1) gives either 0 or 1.
→ (0+0+0)(0+1+1) gives ), as product of 0 with anything is 0
Question 125 
recursive  
recursively enumerable  
NPHard  
None of the above 
Question 126 
The pigeonhole principle  
The divide and conquer technique  
recursion  
Iteration 
→ In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
Question 127 
L={ x^{ n} y^{ n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x^{ +} y^{ +}
i only  
i and ii only  
ii and iii only  
ii only 
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1 :E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X
+
means one or more x’s
Y
+
means one or more y’s
Definition 2 : The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x ^{+} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Question 128 
For the context free grammar G:
R → XRXS, S → aTbTa, T → XTXXϵ X → ab
The strings which are not in L(G) are:
ab,ba,aab
 
abb,aabab
 
a,b,aa
 
a,b,ϵ

Question 129 
0*1 ^{+} 0*1*  
0*1*0 ^{+} 1*  
0*1*0*1 ^{+}  
0^{+}1*0*1* 
Question 130 
(i) The grammar S → SS  a is ambiguous (where S is the start symbol).
(ii) The grammar S → 0S1  01S  e is ambiguous (the special symbol e represents the empty string and S is the start symbol).
(iii) The grammar (where S is the start symbol).
S → T/U
T → x S y ? xy ? e
U → yT
generates a language consisting of the string yxxyy.
Only (i) and (ii) are TRUE  
Only (i) and (iii) are TRUE
 
Only (ii) and (iii) are TRUE  
All of (i), (ii) and (iii) are TRUE 
Option (ii): For producing string 01 it gives 2 parse tree. So, it is also ambiguous.
Option (iii): It is also true
Question 131 
I. p443y
II. p6y
III. 3xyz
IV. p35z
V. p353535x
VI. ppp5
I, III and VI only  
IV, V and VI only  
II, IV and V only  
I, IV and V only 
Given regular expression is p+[35]*[xyz]
It means we have to start with p.
[35]* means (3+4+5)* It can generate these numbers many number of times.
[xyz] → ends with either x or y or z or any combination but not violate order of occurrences
I. p443y → matched because it satisfied above regular expression.
Il. p6y → not matched because 6 not present in regular expression.
III. 3xyz → not matched because it not starts with p.
IV. p35z → matched because it satisfied above regular expression.
V. p353535x → matched because it satisfied above regular expression.
Vl. ppp5 → not matched because it is not end with x or y or z or any combination.
Question 132 
08  
09  
10  
12 
Hence (0^{+}1^{+}  2^{+}3^{+})* = (0^{+}1^{+} + 2^{+}3^{+})* = (a+b)*
Now since the min string in 0^{+}1^{+} is "01" hence "a" has min length two.
Similarly the min string in 2^{+}3^{+} is "23" , hence "b"has min length two.
We require 4 length strings. ^{+} We can generate 4 length strings using "a" only, or using "b" only or using both.^{+} Using "a" one time only → 0^{+}1^{+} only: {0001, 0011, 0111}
using "b" one time only → 2^{+}3^{+} only : {2223, 2233, 2333}
Using two time, i.e., aa, ab, ba, bb
aa→ 0101
ab→ 0123
ba→ 2301
bb→ 2323
'Hence total 10 strings {0001, 0011, 0111, 2223, 2233, 2333, 0101, 0123, 2301, 2323}
Question 133 
The grammar S→aSaSbS∈, where S is the only nonterminal symbol, and ∈ is the null string, is ambiguous.  
An unambiguous grammar has same leftmost and rightmost derivation.  
An ambiguous grammar can never be LR(k) for any k.  
Recursive descent parser is a topdown parser. 
OptionB: FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
OptionC: TRUE: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
OptionD: TRUE: Recursive descent parser is a topdown parser
Question 134 
08  
10  
11  
12 
1111, 0111, 1112, 0122, 0123, 1222, 1223, 0122, 0113, 1123, 0112, 1113.
So, total 12 strings of length 4 are possible.
Question 135 
context free grammar  
context sensitive grammar  
unrestricted grammar  
phrase grammar 
Contextfree grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule
A → α replaces A with α . There can be multiple replacement rules for any given value. For example,
A → α
A → β
means that A can be replaced with either α or β.
→ In contextfree grammars, all rules are onetoone, onetomany, or onetonone. These rules can be applied regardless of context. The lefthand side of the production rule is always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters α and β but not A.
Question 136 
(i) Intersection
(ii) Union
(iii) Complementation
(iv) Kleene Star
then
(i) and (iv)  
(i) and (iii)  
(ii) and (iv)  
(ii) and (iii) 
Note: Except intersection and complementation will closed under all operations in CFL.
Question 137 
S→d/bA
A→d/ccA
bccddd  
aabccd  
ababccd  
abbbd  
None of the above 
OptionA is also wrong because the string generated by grammar is bccccd.
Question 138 
{a}  
{ε, a, b}  
{a, b}  
None of these 
Question 139 
Power of deterministic automata is equivalent to power of nondeterministic automata.  
Power of deterministic pushdown automata is equivalent to power of nondeterministic pushdown automata.  
Power of deterministic turing machine is equivalent to power of nondeterministic turing machine.  
All the above 
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
Question 140 
L = { wwR ǀ wε{0,1}* }  
L = { a ^{n} b^{ n} ǀ n≥0 }  
L = { ww ǀ wε{0,1}* }  
L = { a ^{n} b^{ m} c^{ m} d^{ n} ǀ n,m ≥0 } 
OptionB is correct because we can have a deterministic pushdown automata which will push all the "a" as they come as input and when "b" comes as input for every "b" one "a" will be popped. So in this way we can design a pushdown automata which will accept a n b n . Hence a ^{n} b^{ n} is a CFL.
OptionC is not a CFL because we can't design a pushdown which can accept CFL. Suppose a string "abcabc". Now let's say pushdown automata recognize w=abc after symbol "c" now when "a" come as input after "c" the pushdown automata have to pop "a" i.e. initial input symbol "a" but top of the stack contains "c" as top element. So in this way we can't have any pushdown automata which can accept "ww" language. So it is not a CFL.
OptionD is a CFL because we can design a pushdown automata for a n b m c m d n . The push down automata will push "a" and "b" as the come as input symbol. When "c" came as input then for each "c" one "b" is popped from top of the stack. And when "d" will come as input symbol the top of stack will contain only a's so for every "d" one "a" is popped . In this way we can design a pushdown automata for a ^{n} b^{ m} c^{ m} d ^{n} .
So, optionC is correct answer.
Question 141 
Regular  
Context  Sensitive  
Context free  
None of these 
→ Most general phase structured grammar is context sensitive grammar
Question 142 
Build the symbol table  
Construct the machine code  
Separate mnemonic opcode and operand fields.  
None of these 
Pass1:
1. Assign addresses to all statements in the program
2. Save the values assigned to all labels for use in Pass2
3. Perform some processing of assembler directives
Pass2:
1. Assemble instructions Generate data values defined by BYTE,WORD
2. Perform processing of assembler directives not done in Pass 1
3. Write the object program and the assembly listing
Question 143 
S →AB/AS, A→a/aA, B→b
aa*b +  
aa*b  
(ab)*  
a(ab)* 
It is clearly representing
aa*b
Question 144 
Regular  
Contextsensitive  
Context free  
Syntax tree 
→ Most general phase structured grammar is context sensitive grammar.
Question 145 
S → 0A
A → 1A/0A/1
01100  
00101  
10011  
11111 
Question 146 
S → aB  bA
A → a  as  bAA
B → b  bs  aBB
will generate
odd numbers of a’s and odd numbers of b’s  
even numbers of a’s and even numbers of b’s  
equal numbers of a’s and b’s  
different numbers of a’s and b’s 
Option B is false: as it generate string "ab" which has odd number of a's and b's.
Option D is false: as it always generate one "a" along with one "b". So it will always generate equal number of a's and b's and will never generate different number of a's and b's.
Hence option C is correct.
Question 147 
S → S_{1}S_{3}, S_{1} → aS_{1}c  S_{2} λ,
S_{2} → aS_{2}bλ, S_{3 }→ aS_{3}b S_{4}  λ,
S_{4} → bS_{4}cλ  
S → S_{1}S_{3}, S_{1}→ aS_{1}S_{2}c  λ,
S_{2} → aS_{2}bλ, S_{3} → aS_{3}b S_{4} λ,
S_{4} → bS_{4}cλ  
S → S_{1}S_{2}, S_{1}→ aS_{1}S_{2}c  λ,
S_{2} → aS_{2}b  λ, S_{3} → aS_{3}b  S_{4} λ,
S_{4} → bS_{4}cλ  
S → S_{1}  S_{3}, S_{1}→ aS_{1}cS_{2}  λ,
S_{2} → aS_{2}b  λ, S_{3} → a S_{3}b S_{4}  λ,
S_{4} → bS_{4}c  λ 
Option(A): Option(A) will generate the string "acab" which does not belongs to the sequence a^{n}b^{m}c^{k} . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string "acab" which does not belongs to the sequence a^{n}b^{m}c^{k}. So, it is not the context free grammar for the language L. Option(C): In this option production S_{3} and S_{4} are unreachable so it is not the context free grammar for the language L. Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ........}. So it is the context free grammar for the language L.
Question 148 
L = {wna(w) and nb(w) are both even,
w ∈ {a, b}*} is given by :
(Assume, p, q, r and s are states)
p → aq  br  λ, q → bs  ap r → as  bp, s → ar  bq, p and s are initial and final states.  
p → aq  br, q → bs  ap r → as  bp, s → ar  bq, p and s are initial and final states.  
p → aq  br  λ, q → bs  ap r → as  bp, s → ar  bq p is both initial and final states.  
p → aq  br, q → bs  ap r → as  bp, s → ar  bq p is both initial and final states 
Option (A): The grammar given in this option does not contain a state which is accepting a terminal "λ" , having zero number of "a" and "b". Since the grammar is not accepting λ so it not the regular grammar for the given language L.
Option (B): The grammar given in this option is not generating any string "λ" which is having zero number of "a" and "b". Since the grammar is not generating λ so it not the regular grammar for the given language L.
Option (C): Here state "p" is the initial and final state and the grammar given here is generating string "λ" , having zero number of "a" and "b". Since the grammar is accepting λ so it is the regular grammar for the given language L.
Option (D): In this option (p) is the initial and final state but the grammar is not generating any string "λ" which also belongs to the given language L. So this grammar is not the regular grammar for the given language L.
Question 149 
3  
4  
5  
6 
The minimal DFA accepting the given language L is given below:
Hence the number of states in a minimal deterministic finite automaton corresponding to the language L is 5.
Question 150 
(1 + 010)*  
(01 + 10)*  
(1 + 010)* (0 + λ)  
(1 + 01)* (0 + λ) 
Option A is incorrect because it can generate 010010 string which is having a pair of consecutive zeros.
Option B is incorrect because it can generate 1001 string which is having a pair of consecutive zeros.
Option C is incorrect because it can generate 0100 string which is having a pair of consecutive zeros.
Option D is correct because it will generate all the strings mentioned in the given language L
Question 151 
L1 = {a^{n} b^{l} a^{k}  n + l + k>5 }
L2 = {a^{n }b^{l} a^{k}  n>5, l >3, k≤ l }
Which of the following is true ?
L_{1} is regular language and L_{2} is not regular language.  
Both L_{1} and L_{2} are regular languages.  
Both L_{1} and L_{2} are not regular languages.  
L_{1} is not regular language and L_{2} is regular language 
Question 152 
S → aSc  S_{1} ; S_{1} → bS_{1}c  λ  
S → aSc  S_{1} λ ; S_{1} → bS_{1}c  
S → aSc  S_{1} λ ; S_{1} → bS_{1}c λ  
S → aSc  λ ; S_{1} → bS_{1}c λ 
L1={λ}
L2 is the language when only n=0
L2={bc, bbcc, bbbccc,......}
L3 is the language when only m=0
L3={ ac, aacc, aaaccc, ........}
L4 is the language when n≠0 and m≠0
L4= {abcc, aabbcccc, aaabbbcccccc,...............}
L= {L1 U L2 U L3 U L4}
L= { λ, bc, bbcc, bbbccc,........, ac, aacc, aaaccc,.........., abcc, aabbcccc,aaabbbcccccc,.........}
Option A is incorrect because it does not have any stoping point for condition when m=0 i.e it can't generate strings { ac, aacc, aaaccc, ........}
Option B is incorrect because it does not have any stopping point for condition when n=0 i.e it can't generate strings {bc, bbcc, bbbccc,......}
Option C is correct because it can generate all the strings generated by the language L.
Option D is incorrect because state S1 is unreachable in it. And because of this strings {bc, bbcc, bbbccc,......{abcc, aabbcccc, aaabbbcccccc,...............} can't be generated.
Question 153 
S_{1} is correct and S_{2} is not correct.  
Both S_{1} and S_{2} are correct.  
Both S_{1} and S_{2} are not correct.
 
S_{1} is not correct and S_{2} is correct. 
. Statement S2 is incorrect because equality problem (L1 = L2; where L1 and L2 are CFL) of CFG is undecidable .
Question 154 
Context free language  
Context sensitive language  
Regular language  
None of the above 
Question 155 
Q  
2Q  
2Q – 1  
2Q 
Question 156 
Have the same number of edges  
Have the same number of states  
Recognize the same set of tokens  
Have the same number of states and edges 
Question 157 
any string of odd number of a’s  
any string of odd number of b’s  
any string of even number of a’s and odd number of b’s  
any string of odd number of a’s and odd number of b’s 
L = {ab,ba,ababab, bababa,..........}
Here L is the language containing odd number of a’s and odd number of b’s.
Question 158 
0  
1  
1 or more  
2 or more 
→ So, total of 2 or more auxiliary memory are needed to make a pushdown automata behaves like a Turing machine.
Question 159 
Only context free grammar  
Only regular grammar  
Context free grammar or regular grammar  
Only context sensitive grammar 
B➝ aBb  ab ; Here B is a Context free grammar which can be accepted by the pushdown automata
Question 160 
2n−1  
2n  
n+1  
n ^{2} 
Example:
S → A B
A → a
B → b
Derive string “ab” from above grammar.
Detailed explanation for example:
Using formula 2 n − 1 ; where n = length of string
2 (2) − 1 = 3
Hence the answer is option(1)
Question 161 
Finite state machine  
Deterministic finite automata  
Nondeterministic finite automata  
Linear bounded automata 
L= { a ^{n} b^{ n} c^{ n}  where n > 0 }
is a context sensitive language and cannot be recognized by Finite state machine, Deterministic finite automata, Nondeterministic finite automata but L can be recognized by Linear Bounded Automata.
So Context Sensitive Language can be recognized by Linear Bounded Automata.
Question 162 
Context sensitive  
Context free  
Regular  
None of the above 
→ In case of Context Free grammar we have a stack only in which we can push 0’s as they come as input and can POP 0’s as 1’s come as input but when 2’s comes as input string we have NULL at the top of the stack so this Grammar can’t be a context free grammar.
→ Since in case of Context sensitive grammar we have linear bounded automata and a read/write head which can move backward and upward so this grammar can be accepted by Linear Bounded Automata. So this grammar is a Context Sensitive Grammar.
Question 163 
S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct ?
Both S1 and S2 are correct  
Both S1 and S2 are not correct  
Only S1 is correct  
Only S2 is correct 
→ Halting problem of a turing machine is undecidable because if a turing machine accepts a string then it will halt but if a turing machine does not accept a string then it may or may not halt(can enter infinite loop). So statement S2 is also correct.
Question 164 
S → aaa A; A → aAb  B, B → Bb  λ  
S → aaaAλ, A → aAb  B, B → Bb  λ  
S → aaaA  aa A  λ, A → aAb  B, B → Bb λ  
S → aaaA  aa A  aA  λ, A →
aAb  B, B → Bb  λ

m=0, n<= 3 i.e. L1= { λ, a, aa, aaa}
m=1, n<=4 i.e. L2={ ab, aab, aaab, aaaab}
m=2, n<=5 i.e. L3={abb, aabb, aaabb, aaaabb, aaaaabb} and so on.
Hence L = L1 U L2 U L3 U ...........
L= { λ, a, aa, aaa, ab, aab, aaab, aaaab, abb, aabb, aaabb, aaaabb, aaaabb, .................}
Option(A) is not correct because it can't generate λ.
Option(B) is not correct because it can't generate "a".
Option(C) is not correct because it can't generate "a".
Option(D) is correct because it is generating the language L
.
Question 165 
S_{1} : If L is a regular language then the language {uv  u ∈ L, v ∈ L^{R}} is also regular.
S_{2} : L = {ww^{R}} is regular language. Which of the following is true ?
S_{1} is not correct and S_{2} is not correct.  
S_{1} is not correct and S_{2} is correct.  
S_{1} is correct and S_{2} is not correct.  
S_{1} is correct and S_{2} is correct. 
→ Statement S2 is incorrect. Since the finite state automata do not have a memory element which can remember the previous inputs hence the string "w" can't be recorded in order to match/compare with "w^{R} ". So we can't have a Finite state automata for ww^{R}. And since we can't have Finite state automata for ww^{R} , it means ww^{R} is not a regular language.
Hence the correct option is option(C)
Question 166 
(I). Recursive languages are closed under complementation.
(II). Recursively enumerable languages are closed under union.
(III). Recursively enumerable languages are closed under complementation.
Which of the above statements are true ?
I only  
I and II  
I and III  
II and III 
→ Recursively enumerable languages are closed under union,intersection,etc.., except set difference and complementation.
Question 167 
Contextfree languages are closed under union.  
Contextfree languages are closed under concatenation.  
Contextfree languages are closed under intersection.  
Contextfree languages are closed under Kleene closure 
Contextfree languages are not closed under set difference,Complementation and intersection.
Question 168 
the Pigeonhole principle  
the divide and conquer technique  
recursion  
iteration 
Question 169 
S ⟶ XY
X ⟶ aX  bX  a
Y ⟶ Ya  Yb a
has at least one b  
should end in an ‘a’  
has no consecutive a’s or b’s  
has at least two a’s 
Question 170 
of finite tape length, rewinding capability and unidirectional tape movement.  
of finite tape length, without rewinding capability and unidirectional tape movement.  
of finite tape length, without rewinding capability and bidirectional tape movement.  
of finite tape length, rewinding capability and bidirectional tape movement. 
Question 171 
the output of the former depends on the present state and the current input  
the output of the former depends only on the present state  
the output of the former depends only on the current input  
none of the above 
Question 172 
a*b  
a*baa*  
a*ba*  
None of the above 
L1={ba, baa, baaa, .........................aba, aaba, aaaba,................abaa, abaaa, ....................}
L2={a, ab, abb, abbb, ..........................}
Take "a" from L1:
L1/a ={ b, ba, baa, .................ab, aab, aaab, ....................aba, abaa, .....................}
So we get : a*ba*
If you take "ab" from L2
Like:
L1/ab = you will not get any string i,e. empty set will be in result in case of L1/ab
as no string in L1 end with "ab"
Question 173 
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
5  
4  
3  
2 
Question 174 
(i) a
(ii) aba
(iii) abaabaaba
(iv) abaabaabaabaabaabaabaabaaba
Using this as an information, how would you compare the following regular expressions ?
(i) (aba)^{3x }
(ii) a.(baa)3^{x}–1. ba
(iii) ab.(aab).^{3x}–1.a
(ii) and (iii) are same, (i) is different.  
(ii) and (iii) are not same.  
(i), (ii) and (iii) are different.  
(i), (ii) and (iii) are same.

If you observe all of them is generating (aba)x
Note: This question is ambiguous, the wordings are not very clear.
Question 175 
Regular  
Contextsensitive  
Context free  
None of the above 
→ Most general phase structured grammar is context sensitive grammar.
Question 176 
Context sensitive grammar  
Non context free grammar  
Context free grammar  
None of the above 
Question 177 
Finite state automata  
2way linear bounded automata  
pushdown automata  
both (B) and (C) 
Question 178 
type 0  
type 1  
type 2  
type 3 
Question 179 
Then L(M), the language accepted by the machine M, is the set of all strings having :
two or more b’s.  
three or more b’s.  
two or more a’s.  
three or more a’s. 
Question 180 
Set of all strings containing ‘ab’  
Set of all strings containing ‘aab’  
Set of all strings ending in ‘abab’  
None of the above 
Question 181 
Set of all string not containing ‘11’  
Set of all string not containing ‘00’  
Set of all string containing ‘01’  
Set of all string ending in ‘0’ 
According to the language L generated by given regular expression
Option(A) is incorrect because L contains 110.
Option(B) is correct because no string is containing 00
Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.
Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.
Hence correct answer is option (B)
Question 182 
L = { a^{n} b^{n} n ≥ 1 }  
L = { a^{n} b^{m} c^{n }d^{m}n, m ≥ 1 }  
L = { a^{n} b^{m}n, m ≥ 1 }  
L = { a^{n} b^{m} c^{n}n, m ≥ 1 } 
Language generated in Option (B) requires a memory element and a read write head which can move in both the directions to count equal number of a's and c's , and b's and d's. And since regular languages are accepted by finite automata which does not have a memory element and a read write head which can move in both the directions. Hence Option (A) language is not Regular.
Language generated in Option (C) is regular because number of a's and b's is not necessarily need to be same which means no memory element is required. Hence it is a regular language.
Language generated in Option (D) requires a memory element to count equal number of c's after a. And since regular languages are accepted by finite automata which does not have a memory element. Hence Option (A) language is not Regular. The language generated here is context free language which can be accepted by pushdown automata.
Question 183 
whether two given regular expressions are equivalent  
a given grammar is ambiguous  
a given grammar is regular  
a given grammar is not regular 
Question 184 
To determine if two finite automata are equivalent  
Membership problem for context free grammar  
Finiteness problem for finite automata  
Ambiguity problem for context free grammar 
Question 185 
Only context free grammar  
Only context sensitive grammar  
Only regular grammar  
any unambiguous grammar 
Question 186 
a regular language.  
not a deterministic context free language but a context free language.  
recursive and is a deterministic context free language.  
not recursive.

→ In this way the given language can be accepted by the deterministic pushdown automata and hence the language is deterministic context free language. And when a language is CFL it is also a recursive language.
Hence the correct answer is option (C)
Question 187 
Every recursive language is recursively enumerable.  
L = {0^{n}1^{n} 0^{n} │n=1, 2 , 3, ....} is recursively enumerable.  
Recursive languages are closed under intersection.  
Recursive languages are not closed under intersection. 
TRUE: L = {0^{n}1^{n} 0^{n} │n=1, 2 , 3, ....} is recursively enumerable.
TRUE: Recursive languages are closed under intersection.
→ Recursive closed under union,intersection,complementation,etc.., except Homomorphism and substitution.
FALSE: Recursive languages are not closed under intersection.
→ Recursively enumerable languages are closed under union,intersection,etc.., except set difference and complementation.
Question 188 
Concatenation  
Complementation  
Kleene Star  
Union 
→ Contextfree grammar are not closed under set difference,Complementation and intersection.
Question 189 
Only L_{1} and L_{2} are context free languages  
Only L_{1} and L_{3} are context free languages  
Only L_{2} and L_{3} are context free languages  
L_{1}, L_{2} and L_{3} are context free languages 
→ It means m could be greater than or less than ‘n’ but m will not be equal to ‘n’.
→ Since for accepting the language L1 we need a storage so then no. of a’s can be stored in it and when b’s come as input a’s and b’s can be compared.
→ Since finite automata do not have a storage element hence the language is not regular.
→ Now state transition diagram to check whether L1 is CFL or not:
→ Hence L_{2} is also a CFL.
L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Question 190 
(A) Strings of even number of a’s.
(B) Strings of a’s, whose length is a prime number.
(C) Set of all palindromes made up of a’s and b’s.
(D) Strings of a’s whose length is a perfect square.
(A) and (B) only  
(A), (B) and (C) only  
(B), (C) and (D) only  
(B) and (D) only 
For even no. of a’s finite automata can be constructed so it is regular.
Option (B):
L = { a^{2}, a^{3}, a^{5}, a^{7}, a^{11}, a^{13}, a^{17}...................}
It is not regular language. A language is regular if the difference between two consecutive strings is same or we can say the language is in AP(arithmetic progression). But here if you see the difference between two consecutive strings/terms is not same. Hence it is not regular.
Statement (C):
L = {ab, aabb, ................... abab, baba, ababa, aababa, baabb, ..................}
It is also not regular language because the difference between two consecutive strings/terms is not same.
Statement (D): L = { a^{1}, a^{4}, a^{9}, a^{16}, a^{25}, a^{36}, a^{49}...............}
It is also not regular language because the difference between two consecutive strings/terms is not same.
Question 191 
{∈}  
{∈, 1}  
ϕ  
1* 
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 192 
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?
Both (A) and (B) are false.  
Both (A) and (B) are true.  
(A) is true, (B) is false.  
(A) is false, (B) is true. 
So here, Statement (A) is true because regular language, context sensitive language and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable language is closed under union but not under complementation but still it is closed under intersection.
Statement (B): The meaning of given statement is that if a class of languages that is closed under union and intersection then it has to be closed under complementation but if a language is not closing under either of union or intersection then it can or can not be closed under complementation.
So here, Statement (B) is false because regular language, context sensitive language, recursive language and recursively enumerable language are closed under union and intersection but only regular language, context sensitive language and recursive language are closed under complementation , recursively enumerable language is not closing under complementation after being closed under union and intersection.
Hence statement (B) is not true.
Question 193 
log_{K}W ≤ h ≤ log_{K}((W1) / k1)  
log_{K}W ≤ h ≤ log_{K}(KW)  
log_{K}W ≤ h ≤ K log_{K}W  
log_{K}W ≤ h ≤ ((W1) / k1) 
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log_2 (W+1)
so in general it should be log_k ((w1) / (k1))
Question 194 
Both L_{1} and L_{2} are not context free language  
Both L_{1} and L_{2} are context free language.  
L_{1} is context free language, L_{2} is not context free language.  
L_{1} is not context free language, L_{2} is context free language. 
Hence L1 is a context free language.
Statement 2: L2 is not a context free language because we can push a's on the top of stack and when b's came as input we can pop one "a" for each "b" so in this way stack will get empty before comparing equal number of a, b and c. For comparing number of "c" the will be no "a or b" on the top of stack.
Hence L2 is not a context free language.
Question 195 
A. L = {wn_{a}(w) = n_{b}(w)} is deterministic context free language, but not linear.
B. L = {a^{n} b^{n}} ∪ {a^{n} b^{2n}} is linear, but not deterministic context free language.
Which of the following options is correct ?
Both (A) and (B) are false.  
Both (A) and (B) are true.  
(A) is true, (B) is false.  
(A) is false, (B) is true. 
A linear grammar is a context free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.
ex1: S→ aSb  ab
ex2: S→ aS  Sb  ϵ
The grammar for (a)> S→ϵ,S→SaSbS,S→SbSaS }
which is not linear. It is DCFL
Statement2:
The example grammar is
S→ aSb  aSbb  ϵ
Hence it is linear language and it is not DCFL.
Question 196 
Singletapeturing machine and multidimensional turing machine.  
Multitape turing machine and multidimensional turing machine.  
Deterministic pushdown automata and nondeterministic pushdown automata.  
Deterministic finite automata and Nondeterministic finite automata 
Option(B): is also incorrect because both machines are same so they can accept the same string with same speed.
Option(C) : It is correct option because Non deterministic pushdown automata is more powerful than deterministic pushdown automata because by using nondeterministic pushdown automata L= {ww  w belongs to (a,b)*} can be accepted but the same language can't be accepted using deterministic pushdown automata.
Option(D) : it is incorrect option because DFA and NDFA both are equivalent to each other i.e. we can convert DFA into NFA and NFA into DFA. DFA and NFA are equal in powers and can accept the same strings.
Question 197 
Every contextsensitive language is recursive.  
The set of all languages that are not recursively enumerable is countable.  
The family of recursively enumerable languages is closed under union.  
The families of recursively enumerable and recursive languages are closed under reversal. 
Option(B): It is incorrect option.
Option(C): Yes it is true that recursively enumerable languages are closed under union.
Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.
NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.
Question 198 
S → S_{1}  S2 S_{1} → a S_{1} A_{1} A_{1} → b A_{1} λ S_{2 }→ aaS_{2} A_{2 } A_{2} → b A_{2} λ  
S → S_{1 } S_{2} S_{1 }→ a S_{1} aA_{1} S_{2} → aaS_{2}  A_{2} A_{1} → b A_{1} λ A_{2} → b A_{2} λ  
S → S_{1}  S_{2} S_{1 }→ aaa S_{1} aA_{1} S_{2} → aaS_{2} A_{2} A_{1} → b A_{1} λ A_{2} → b A_{2} λ  
S → S_{1}  S_{2} S_{1} → aa S_{1 } A_{1} S_{2} → aaS_{2}  aA_{2} A_{1} → bbA_{1}  λ A_{2} → bbA  b 
Option(A) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S_{1}
S_{1} → a S_{1}
S_{1} → aa S_{1}
S_{1} → aaA_{1}
S_{1} → aab A_{1}
S_{1} → aabλ
Option(B) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S_{1}
S_{1} → a S_{1}
S_{1} → aaA_{1}
S_{1} → aabA_{1}
S_{1} → aabλ
Option(C) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S_{2}
S_{2} → aaS_{2}
S_{2} → aaA_{2}
S_{2} → aabA_{2} λ
S_{2} → aabλ
Option(D) is correct because it generates strings like {ab, aabb, aaab,..........}
Question 199 
{λ, a, b, ab, ba} ∪ {w∈{a, b}*  w > 3}  
{a, b, ab, ba} ∪ {w∈{a, b}*  w > 3}  
{w ∈ { a, b}*  w > 3} ∪ {a, b, ab, ba}  
{λ, a, b, ab, ba} ∪ {w ∈ {a, b}*  w ≥ 3} 
Here L= {aa,bb}
It means complement of L can contain { λ, a, b, ab, ba, aaa, aab, aba, bba,..................}
Hence Option (D) is correct.
Question 200 
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true?
(a) and (b) only  
(b) and (c) only  
(c) and (a) only  
(a), (b) and (c) 
∅* = ε
ε* = ε
RR* = R*R
R*R* = R*
(R*)* = R*
RR* = R*R
(PQ)*P =P(QP)*
(r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)*
Hence option(D) is correct.
Question 201 
L_{1} = {uww^{R}ν  u, v, w ∈ {a, b}^{+}}
L_{2} = {uww^{R}ν  u, ν, w ∈ {a, b}+, u > ν}
Which of the following is correct ?
L_{1} is regular language and L_{2} is not regular language.  
L_{1} is not regular language and L_{2} is regular language.  
Both L_{1} and L_{2} are regular languages.  
Both L_{1} and L_{2} are not regular languages. 
Question 202 
0* 1*  
00*  
10*  
1*0* 
Question 203 
h<((W  1)/k1)  
log_{k}W < h  
log_{k}W < h < ((W  1)/k1)  
log_{k}W <= h <= ((W  1)/k1) 
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log_{2}W+1)
So, in general it should be log_{k}((w1) / (k1))
Question 204 
(λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)*  
(λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)*  
(λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)*
 
(λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)* 
Question 205 
L_{1} is regular and L_{2}* is not regular  
L_{1} is not regular and L_{2}* is regular  
Both L_{1} and L_{2}* are regular languages  
Both L_{1} and L_{2}* are not regular languages 
A language could be regular if the difference between two consecutive terms is in G.P. But here L_{1} does not contains the strings in G.P form. Hence it is not regular language.
L_{2} is any subset of 0* because any subset of 0* could be {0}, {00}, {000}, {0000}, {0,00}, {0,00,000} ............... and we can have a finite automata which can accept all these subsets. Hence L2 is a regular language.
Question 206 
2  
4  
5  
6 
Question 207 
L’ is context free and L^{k} is not context free for any k ≥ 1.  
L’ is not context free and L^{k} is not context free for any k ≥ 1.  
Both L’ and L^{k} is for any k ≥ 1 are context free.  
Both L’ and L^{k} is for any k ≥ 1 are not context free. 
Question 208 
aa*b  
abab  
aba*b  
aba* 
Question 209 
Which of the following is not an example of a string in A?
011  
0111  
0011  
001111 
A=ε
If n=1
A=1
If n=2
A=011
If n=3
A=0111
If n=4
A=001111
So, A={ε,1,011,0111,001111,...}
Hence, options(C) is not an example of a string in (A)
Question 210 
closed, not closed  
not closed, not closed  
closed, closed  
not closed, closed 
Hence the correct option is (C)
Question 211 
(a)(i), (b)(ii), (c)(iii), (d)(iv)  
(a)(i), (b)(ii), (c)(iv), (d)(iii)  
(a)(iv), (b)(iii), (c)(ii), (d)(i)
 
(a)(iv), (b)(iii), (c)(i), (d)(ii) 
The given language {a^{n }b^{n} a^{n.  n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly. Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation {an bn an} is context sensitive language but not context free language, the logic is the same as above. SInce for given language can’t be accepted by pushdown automata, so it is not a context free language.}
Question 212 
two  
three  
four  
five 
Question 213 
S → XYX
X → aXbXλ
Y → bbb
generates the language which is defined by regular expression:
(a + b)*bbb  
abbb(a + b)*  
(a + b)*(bbb)(a + b)*  
(a + b)(bbb)(a + b)* 
Option(B) is incorrect because "bbbb(a+b)* can also be generated by given grammar.
Option (C) is correct because S → XYX X → aXbXλ Y → bbb , here "bbb" will be in middle and X → aXbXλ can generate (a+b)* and since S → XYX is having "X" before and after "Y" so it is correct.
Option (D) is not correct because X → aXbXλ can generate (a+b)^* and since S → XYX is having "X" before and after "Y" so we can have (a+b)* before and after "bbb"
Question 214 
64  
56  
1024  
5832 
Question 215 
L_{1 }is context free language and L_{2 }is not context free language  
L_{1 }is not context free language and L_{2 }is context free language
 
Both L_{1} and L_{2 }are context free languages  
Both L_{1} and L_{2 }are not context free languages 
L2 is not CFL because we can push all a's first on the top of stack when a "b" come as input change the state and don't push "b" on stack now when "a" comes after "b" then for each "a" pop one "a" from top of stack. . Bur for "b" that comes in last we don't have "a" to compare them. So it is not CFL language.
Question 216 
(a) G is a CFG with L(G)=∅
(b) There exist two TMs M1 and M2 such that L(M) ⊆{L(M1)UL(M2)}= language of all TMs
(c) M is a TM that accepts w using a most 2^{w} cells of tape
(a) and (b) only  
(a) only  
(a), (b) and (c)  
(c) only 
(b): Recursive: The reason is we can assume L(M2)=∑* and hence any TM (M1) will be definitely subset of L(M2). So we only need to see that M1 is a valid Turing machine and no need to check whether it is subset of L(M2) as it is obviously subset of L(M2)=∑*. Checking validity of Turing machine is always a halting process, hence it is recursive.
(c): L={(M,w)M is a TM that accepts w using at most 2^{w} squares of its tape}.
Recursive: Let m be he number of states in M, and k be the size of the alphabet that M uses, and r=w. If M uses at most 2^{r} squares of its tape, then there are at most Alpha=mK^{2r} 2^{r} configurations(why?). If M runs on w for more than α steps, and does not use more than 2^{r} squares of its tape, then M must be in the one configuration at least twice(pigeonhole principle), in which case M would enter an infinite loop on input w. Based on this, we design a machine M* that decides L that works as follows:
M* runs M on w for at most α+1 steps.
If M accepts w which steps with using at most 2^{r} squares, M* halts and accepts.
If M rejects w within α steps with using at most 2^{r} squares, M* halts and rejects.
If M goes beyond 2^{r} squares, M* halts and rejects.
If M does not halt and does not go beyond 2^{r} squares, M* rejects.
Note: To know the definition of configurations and the details, reader may refer to "Introduction to theory of computation Michael Sipser, Chapter 8 Space complexity)
Question 217 
A language L ⊆ Σ* is recursive if there exists some Turing machine M
Which of the following conditions is satisfied for any string w?
If w ε L, then m accepts w and M will not halt  
If w ∉ L, then M accepts w and M will halt by reaching at final state  
If w ∉ L, then M halts without reaching to acceptable state  
If w ε L, then M halts without reaching to an acceptable state 
Hence option 3 is correct.
Question 218 
Where L1 : Regular language
L2 : Contextfree language
L3 : Recursive language
L4 : Recursively enumerable language
ListI List2
(a) L'_{3} U L_{4} (i) Contextfree language
(b) L'_{2} U L_{3} (ii) Recursively enumerable language
(c) L_{1}* ∩ L_{2} (iii) Recursive language
Choose the correct from those given below:
(a)(ii); (b)(i); (c)(iii)  
(a)(ii); (b)(iii); (c)(i)  
(a)(iii); (b)(i); (c)(ii)  
(a)(i); (b)(ii); (c)(iii) 
Hence (a) matches with (ii).
(b): Context free language are not closed under complement operation. So consider L2 as recursive language because context free languages are also recursive language so we can say that L2 is recursive language and we know that recursive languages are closed under complement operation.
Now union of ~L2 and L3 will result in recursive language because both ~L2 and L3 are recursive language and recursive languages are closed under union operation.
Hence (b) matches with (iii)
(c): L1 is regular language and regular languages are closed under kleene closure operation.
Hence L 1 * is a regular language. And intersection of L 1 and L 2 results into a regular language.
But, since all regular languages are context free language then we can say that intersection of L 1 and L 2 results into a context free language.
Hence (c) matches with (i).
Question 219 
(a) By Constructing redundant CFG in CNF generating language L
(b) By constructing nonredundant CFG G in CNF generating language L
(c) By constructing nonredundant CFG in CNF generating language L{∧} (∧ stands for null)
Which of the following is correct?
(a) only  
(b) only  
(c) only  
None of(a),(b) and (c) 
L(G') is finite if and only if L(G) is finite. A simple test for finiteness of a CNF grammar with no useless symbols is to draw a directed graph with a vertex for each variable and an edge from A and B if there is a production of the form A→BC or A→ CB for any C. Then the language generated is finite if and only if this graph has no cycles.
Question 220 
regular expression is a*b(a+b)
1  
2  
3  
4 
Please note: it is asked about minimum finite automata (so its about min NFA and not min DFA)
Question 221 
S→ XY
X→ YaY  a and y → bbX
Which of the following statements is/are true about the above grammar?
(a) Strings produced by the grammar can have consecutive three a's
(b) Every string produced by the grammar have alternate a and b
(c) Every string produced by the grammar have at least two a's
(d) Every string produced by the grammar have b's in multiple of 2.
(a) only
 
(b) and (c) only
 
(d) only
 
(c) and (d) only

Statement (a) is not correct because the grammar can generate two consecutive a’s but not three consecutive a’s.
Statement (b) is not correct because the grammar can generate two b’s together it means that there is no alteration of “a” and “b”.
Statement (c) is correct because every string produced by the grammar have at least two a's. Statement (d) is correct because every string produced by the grammar have b's in multiple of 2.
Question 222 
1 final state among 5 states  
4 final states among 5 states  
1 final state among 6 states  
5 final states among 6 states 
Question 223 
(1 + 01) * (10 + 01)  
(1 + 01) * 01  
(1 + 01) * (1 + 01)  
(10 + 01) * 01 
Option(A) is not correct because it can generate “10” which is not ending with “1”.
Option(B): It can’t generate “1” which is a string belongs to given language L. So it is not a correct option.
Option(C) : It is the correct option because it can generate all the strings generated by a given language.
Option(D): It is not the correct answer because it can’t generate strings like 1,11,........
Question 224 
q _{0} and q_{ 0} respectively  
q _{0} and q_{ 1} respectively  
q _{0} and q_{ 2} respectively  
q _{0} and q_{ 3} respectively 
Question 225 
S → 0  0 S  1 S S  
S → 0 S  1 S  0 S S  1 S S  0  1  
S → 0  0 S  1 S S  S 1 S  S S 1  
S → 0 S 1 S  0  1 
L= { 0, 00, 000, 100, 001, 010,...........}
Option(A) is incorrect because can’t generate string “001”
Option(B) is incorrect because it is generating string”1” in which number of 0’s is less than number of 1’s.
Option(C) is correct because it can generate all the strings generated by the given language L.
Option(D) is incorrect because it is generating string”1” in which number of 0’s is less than number of 1’s.
Question 226 
S 1 :If L 1 and L 2 are recursively enumerable languages over ∑, then L 1 ∪ L 2 and L 2 ∩ L 2 are also recursively enumerable.
S 2 : The set of recursively enumerable languages is countable. Which of the following is correct ?
S 1 is correct and S 2 is not correct  
S 1 is not correct and S 2 is correct  
Both S 1 and S 2 are not correct.  
Both S 1 and S 2 are not correct. 
Statement S 2 is true because recursively enumerable languages are those languages for which we can have a Turing machine but we can’t say whether the Turing machine will halt on some input or not. Since the set of all Turing machines is countable, hence set of all recursively enumerable languages is also countable.
Question 227 
G 1 : S → ABaaB
A → aA  ∈
B → bB  ∈
G2: S → AB
A → aAb  ab
B → abB  ∈
Which of the following is correct?
G 1 is ambiguous and G 2 is unambiguous grammars  
G 1 is unambiguous and G 2 is ambiguous grammars  
both G 1 and G 2 are ambiguous grammars  
both G 1 and G 2 are unambiguous grammars 
G2 is ambiguous because for generating string ab we are having two different leftmost trees.
NOTE: A grammar is ambiguous only if it can generate two different trees(either leftmost derivation tree or rightmost derivation tree) for a same string.
Question 228 
(K – 1) P + T  1  
(K – 1) P + T  
K P + T  1  
K P + T 
Question 229 
L_{1} = {a^{n}b^{n}c^{m}} ∪ {a^{n} b^{m} c^{m}}, n. m ≥ o
L_{2} = {ωω^{R} ω ∈ {a, b}*} Where R represents reversible operation.
Which one of the following is (are) inherently ambiguous language(s)?
only L_{1}  
only L_{2}  
both L_{1} and L_{2}  
neither L_{1} nor L_{2} 
Question 230 
If L is the regular language denoted by T= (w + x*)(ww)*, then the regular language h(L) is given by
(z x yy + xy) (z x yy)  
(zxyy + (xzy)*) (zxyy zxyy)*  
(zxyy + xyz) (zxyy)*  
(zxyy + (xzy)* (zxyy zxyy) 
Question 231 
Only S_{1}  
Only S_{2}  
Both S_{1} and S_{2}  
Neither S_{1} nor S_{1} 
Statement S2 is correct because subset problem of recursively enumerable languages is undecidable.
Question 232 
S→0A0BB
A→00A λ
B→1B11C
C→B
Which language does this grammar generate?
L(00) * 0+(11)*1)  
L(0(11)* + 1(00)*)  
L((00)*0)  
L(0(11) *1) 
Question 233 
Let A = (001, 0011, 11, 101} and B = (01, 111, 111, 010}. Similarly, let C = {00, 001, 1000} and D = {0, 11,011}.
Which of the following pairs have a postcorrespondence solution?
Only pair (A, B)  
Only pair (C, D)  
Both (A, B) and (C, D)  
Neither (A, B) nor (C, D) 
The Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows −
Given the following two lists, M and N of nonempty strings over ∑ −
M = (x_{1}, x_{2}, x_{3},………, x_{n})
N = (y_{1}, y_{2}, y_{3},………, y_{n})
We can say that there is a Post Correspondence Solution, if for some i_{1},i_{2},………… i_{k}, where 1 ≤ i_{j} ≤ n, the condition x_{i1} …….x_{ik} = y_{i1} …….y_{ik} satisfies.
Question 234 
Consider the following grammars :
Which of the following is correct w.r.t. the above grammars?
G_{1} and G_{3} are equivalent  
G_{2} and G_{3} are equivalent  
G_{2} and G_{4 }are equivalent  
G_{3 } and G_{4} are equivalent 
Question 235 
Consider the following language families :
L1 = The context – free language
L2 = The context – sensitive language
L3 = The recursively enumerable language
L4 = The recursive language
Which one of the following options is correct?
L_{1} ⊆ L_{2} ⊆ L_{3} ⊆ L_{4}  
L_{2} ⊆ L_{1} ⊆ L_{3} ⊆ L_{4}  
L_{1} ⊆ L_{2} ⊆ L_{4} ⊆ L_{3}  
L_{2 ⊆ L1 ⊆ L4 ⊆ L3} 
Question 236 
S →aA a,A → aAb b  
S → aaA λ, A → aAbλ  
S → aaaA a, A → aAbλ  
S → aaaA λ, A → aAbλ 
Question 237 
Consider the following statements with respect to the language L = {a^{n}b^{n}  n ≥ 0}
Which one of the following is correct?
only S_{1} and S_{2}  
only S_{1} and S_{3}  
only S_{2} and S_{3}  
S_{1}, S_{2} and S_{3} 
Since context free languages are closed under kleen closure so L^{k} is contextfree language for any given k ≥ 1. Hence S2 is correct.
Complement of given language L will be a language accepting all strings other than {a^{n}b^{n}  n ≥ 0}. And we can easily design a pushdown automata which rejects {a^{n}b^{n}  n ≥ 0} and accepts all string other than this. And as we know, context free languages are closed under kleen closure. Hence S3 is correct.
Question 238 
Type 3
 
Type 1  
Type 0  
Type 2 
Question 239 
L= {a,ab,ab^{2},...}  
L= {a^{m}b^{n}:m,m>0,n>0}  
L= {a^{m}b^{m}:m>0}  
L= {b^{m}ab^{n}:m0,n0} 
→Example :
m=1 ⇒ ab
m=2⇒ aabb and so on.
Question 240 
r= a*b*c  
r= aa*bb*c  
r= aa*b*cc  
r= aa*bb*cc* 
→Substitute in r=s=t=1 in w then L= abc
→So option D gives the regular expression abc
Question 241 
Union , intersection  
Union , kleene closure  
Intersection, complement  
Complement, kleene closure 
Question 242 
Every subset of a regular set is regular  
Every finite subset of nonregular set is regular  
The union of two non regular set is not regular  
Infinite union of finite set is regular 
Question 243 
Strings that begin and end with the same symbol  
All odd and even length palindromes  
All odd length palindromes  
All even length palindromes 
So the grammar generate odd length palindrome.
Question 244 
3  
4  
5  
6 
Question 245 
A→ BC
B→ x  Bx
C→ B  D
D→ y  Ey
E→ z
The nonterminal alphabet of the grammar is
{A,B,C,D,E}  
{B,C,D,E}  
{A,B,C,D,E,x,y,z}  
{x,y,z} 