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 
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 7 
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 8 
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 9 
(L + D)*  
(L.D)*  
L(L + D)*  
L(L.D)* 
Question 10 
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 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 
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 37 
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 38 
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 39 
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 40 
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 41 
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 42 
Regular  
Context free but non regular  
Context sensitive but non context free  
Type 0 but non context sensitive 
Question 43 
(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 44 
(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 45 
finite state automaton  
2way linear bounded automata  
pushdown automata  
Both (B) and (C) 
Question 46 
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 47 
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 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 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 51 
1.∅
2.{∈}
3.a*
4.{a, ∈}
1  
2  
3  
4 
Hence the complement of language is: {a* − a+} = {ϵ}
Question 52 
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 53 
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 54 
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 55 
 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 56 
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 57 
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 58 
a*b*  
(a  b)*  
(ab) *  
(a  b*) 
Question 59 
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 60 
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 61 
Finite automata  
Pushdown automata  
Non deterministic turing machine  
Non deterministic PDA 
Question 62 
Given problems is computable  
Given problem is non computable  
Given problem has finite state solution  
Given problem is solved in polynomial time. 
Question 63 
(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 64 
regular language  
context free language  
context sensitive language  
recursive enumeration language 
Question 65 
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 66 
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 67 
Union  
Concatenation  
Kleene's closure  
All of these 
Question 68 
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 69 
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 70 
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 71 
No  
Yes  
Sometimes  
Depends on NFA 
Question 72 
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 73 
L1L2 is not context free  
L1 intersection L2 is context free  
~L1 is context free  
Both (A) and (C) 
Question 74 
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 75 
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 76 
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 77 
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 78 
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 79 
(0+1+0+1+0+1+0+1)^{4}  
(0+1)^{4}  
(01)^{4}  
(0+1+ɛ)^{4} 
Question 80 
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 81 
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 82 
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 83 
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 84 
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 85 
Unambiguous CFG  
Ambiguous CFG  
Not a CFG  
Deterministic CFG 
Question 86 
Regular  
Context free but not regular  
Recursive but not necessarily context free  
Recursively enumerable but not necessarily recursive 
Question 87 
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 88 
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 89 
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 90 
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 91 
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 92 
(00+(11)*0)  
1(0+1)*101  
(10)*(01)*(00+11)*  
110*(0+1) 
Question 93 
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 94 
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 95 
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 96 
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 97 
Pushdown automata  
Turing machine  
Linear Bounded Automata  
None of the options 
→ NPDA is more powerful than DPDA.
Question 98 
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 99 
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 100 
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 101 
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 102 
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 103 
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 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 
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 105 
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 106 
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 107 
Type 0  
Type 1
 
Type 2  
Type 3 
Question 108 
{0,1,01,ɛ}  
{0,1,ɛ}  
{0,1,01,11,00,10,ɛ}  
{0,1} 
Question 109 
DFA>NFA  
NFA>DFA
 
Equals  
Can't be said 
Question 110 
16  
26  
32  
64 
=2^{2}*2^{4}
=4*16
=64
Question 111 
π  
∅  
a  
b 
Question 112 
1  
0  
2  
none of the options 
Question 113 
(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 114 
recursive  
recursively enumerable  
NPHard  
None of the above 
Question 115 
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 116 
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 117 
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 118 
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 119 
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 120 
0*1 ^{+} 0*1*  
0*1*0 ^{+} 1*  
0*1*0*1 ^{+}  
0^{+}1*0*1* 
Question 121 
(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 122 
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 123 
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 124 
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 125 
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 126 
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 127 
(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 128 
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 129 
{a}  
{ε, a, b}  
{a, b}  
None of these 
Question 130 
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 131 
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 132 
Regular  
Context  Sensitive  
Context free  
None of these 
→ Most general phase structured grammar is context sensitive grammar
Question 133 
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 134 
S →AB/AS, A→a/aA, B→b
aa*b +  
aa*b  
(ab)*  
a(ab)* 
It is clearly representing
aa*b
Question 135 
Regular  
Contextsensitive  
Context free  
Syntax tree 
→ Most general phase structured grammar is context sensitive grammar.
Question 136 
S → 0A
A → 1A/0A/1
01100  
00101  
10011  
11111 
Question 137 
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 138 
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 139 
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 140 
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 141 
(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 142 
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 143 
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 144 
(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 145 
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 146 
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 147 
(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 148 
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 149 
(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 150 
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 151 
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 152 
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 153 
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 154 
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 155 
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 156 
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 157 
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 158 
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 159 
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 160 
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 161 
Context free language  
Context sensitive language  
Regular language  
None of the above 
Question 162 
Q  
2Q  
2Q – 1  
2Q 
Question 163 
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 164 
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 165 
(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 166 
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 167 
the Pigeonhole principle  
the divide and conquer technique  
recursion  
iteration 
Question 168 
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 169 
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 170 
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
5  
4  
3  
2 
Question 171 
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 172 
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 173 
(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 174 
Regular  
Contextsensitive  
Context free  
None of the above 
→ Most general phase structured grammar is context sensitive grammar.
Question 175 
Context sensitive grammar  
Non context free grammar  
Context free grammar  
None of the above 
Question 176 
Finite state automata  
2way linear bounded automata  
pushdown automata  
both (B) and (C) 
Question 177 
type 0  
type 1  
type 2  
type 3 
Question 178 
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 179 
Set of all strings containing ‘ab’  
Set of all strings containing ‘aab’  
Set of all strings ending in ‘abab’  
None of the above 
Question 180 
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 181 
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 182 
whether two given regular expressions are equivalent  
a given grammar is ambiguous  
a given grammar is regular  
a given grammar is not regular 
Question 183 
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 184 
Only context free grammar  
Only context sensitive grammar  
Only regular grammar  
any unambiguous grammar 
Question 185 
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 186 
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 187 
Concatenation  
Complementation  
Kleene Star  
Union 
→ Contextfree grammar are not closed under set difference,Complementation and intersection.
Question 188 
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.