# Theory Of Computation | Subject Wise

## Theory-of-Computation

 Question 1
A language with string manipulation facilities uses the following operations.
• head(s)              -  returns the first character of the string s
• tails(s)               -  returns all but the first character of the string s
• concat(sl, s2)  -  concatenates string s1 with s2.
 A Ab B Ba C Ac D As
Question 1 Explanation:
Given
s=acbc
head(s) = First character of the string of the string
tail(s)    = All Except first character of the string
concat(a,b)
ab
 Question 2
Choose the correct statement:
 A A = {an bn | n = 1, 2, 3, …. } is a regular language B 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 C L(A * B) ∩ B gives the set A D None of the above
Question 2 Explanation:
option(A)=False
A={anbn ∣ n = 1,2,3,…}  it is deterministic context free language(DCFL) not regular because it generates  number of a's equal to number of  b's. example: { ab, aabb, aaabbb, , , ,  anbn  }

option(B) = False
Equal number of a's and Equal number of b's is also Deterministic Context Free Language(DCFL) but not regular Language.

option(C) = False
L(AB) ∩ B gives the set B not set A
L(A*B)= L( { B + AB + AAB + AAAB + ......B} ) // B always there in A*B
L(A*B) ∩ B = B
 Question 3
CFG (Context Free Grammar) is not closed under
 A Union B Complementation C Kleene star D Product
Question 3 Explanation:
CFL are closed under union, concatenation(product) and kleene closure but not closed under intersection and complementation
 Question 4
The FSM (Finite State Machine) machine pictured in the figure below A Complements a given bit pattern B Finds 2’s complement of a given bit pattern C Increments a given bit pattern by 1 D Changes the sign bit
Question 4 Explanation:
Small correction in the diagram Increments a given bit pattern by 1.

Table analysis for the above diagram Question 5
A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A→ BC or A→ a.
Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
 A 2x – 1 B 2x C 2x + 1 D 2x
Question 5 Explanation:
In CNF to derive a string of terminals of length x, Number of productions in derivation is 2x - 1
In GNF to derive a string of terminals of length x, Number of productions in derivation is
 Question 6
Consider the grammar
S → ABCc ∣ bc
BA → AB
Bb → bb
Ab → ab
Aa → aa
Which of the following sentences can be derived by this grammar?
 A abc B aab C abcc D abbc
Question 6 Explanation:
C is a useless symbol in S → ABCc and it cannot derive any terminal so remove it
S→ABc // now removed
Let see remaining productions
Bb → bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
∴S→ABc→abc
 Question 7
Given the following statements:
S1 : Every context-sensitive language L is recursive
S2 : There exists a recursive language that is not context-sensitive
Which statements are true?
 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are not correct D Both S1 and S2 are correct
Question 7 Explanation:
According to Chomsky Hierarchy
S1 is True = Context Sensitive Languages are the subset of recursive languages
S2 is True = Recursive languages are the superset of Context Sensitive Languages and it is not necessary that every Recursive language is Context Sensitive Languages. Question 8
Which one of the following is FALSE?
 A There is a unique minimal DFA for every regular language B Every NFA can be converted to an equivalent PDA C The complement of every context-free language is recursive D Every non-deterministic PDA can be converted to an equivalent deterministic PDA
Question 8 Explanation:
(A) There is unique minimal DFA for every regular language - TRUE

(B) Every NFA can be converted to an equivalent PDA. TRUE
Every Regular Language is CFL, so we can draw PDA for regular language also.

(C) Complement of every context-free language is recursive. TRUE
CFL is a proper subset of recursive languages and recursive languages are closed under complement.

(D) = FALSE
Non-deterministic PDA is more powerful then Deterministic PDA. So, DPDA cannot handle languages/grammars with ambiguity but NDPDA can handle ambiguity languages/grammar  and DPDA is a proper subset of NDPA. so every DPDA can be converted to an equivalent NPDA(but reverse is not possible)
 Question 9
In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
 A (L + D)* B (L.D)* C L(L + D)* D L(L.D)*
Question 9 Explanation:
L(L + D)* is valid identifier because it start with only letter(L) and it followed by (L + D)* means any number of letters or digits
 Question 10
If L and P are two recursively enumerable languages, then they are not closed under
 A Kleene Star L * of L B Intersection L ∩ P C Union L ∪ P D Set Difference
Question 10 Explanation:
Recursively enumerable languages are closed under Intersection
Recursively enumerable languages are not closed under complement
Set difference= L−P can be written as L ∩ PC. where PC is complement of P so Set difference of these two language is not closed.
 Question 11
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
 A Set of strings with 2 a’s and 2 b’s B Set of strings with 2 a’s 2 b’s followed by b C Set of strings with 2 a’s followed by b’s which is a multiple of 3 D Set of strings with even number of a’s followed by odd number of b’s
Question 11 Explanation:
In the given regular expression r=(aa)(bb)b contains Kleene star(*)  where * means 0 or more occurrences
(aa)(bb)b = {b, , , ,, }
So, string "b" must accepted by r=(aa)∗(bb)∗b

So we can strike of option(A),option(B),option(C)
 Question 12
Consider the grammar with productions S → aSb | SS | ϵ This grammar is
 A Not context-free, not linear B Not context-free, linear C Context-free, not linear D Context-free, linear
Question 12 Explanation:
In linear grammar in which all non-terminals should be only in left side (Left linear) or right side (Right linear)
In left-linear or left regular grammars, in which all non-terminals in right hand sides are at the left ends.
In right-linear or right regular grammars, in which all non-terminals in right hand sides are at the right ends.
S→aSb  the non terminal S appears in middle. so It is not linear grammar

Context free grammar (CFG) are with each productions follows production rules A → B, where A single non-terminal and B is the set of terminal and non-terminal.
In CFG non terminal can appear (in left, right or in between of RHS).
 Question 13
Identify the language generated by the following grammar
S -> AB
A -> aAb|ϵ
B -> bB| b
 A {ambn | n>=m, m>0} B {ambn | n>=m, m>=0} C {ambn | n>m, m>0} D {ambn | n>m, m>=0}
Question 13 Explanation:
The language generated by the following grammar is L={b,bb,bbb, abb, abbbbb, ababbbb} = { ambn ∣ n>m, m≥0 }
Which is Equal to option(D)
 Question 14
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive.
Which one of the following statements is false?
 A L1 ∩ L2 is context-free B L3 ∩ L1 is recursive C L1 ∪ L2 is context-free D L1 ∩ L2 ∩ L3 is recursively enumerable
Question 14 Explanation:
Given
L1 be regular language(RL)
L2 be a deterministic context free language (DCFL)
L3 a recursively enumerable language(REL) but not Recursive

option(A) = True
L1∩L2 = RL ∩ DCFL = DCFL which is CFL

option(B) = False
L3∩L1 = REL ∩ Regular = REL but may or may not RECURSIVE

option(C) = True
L1∪L2 = RL ∪ DCFL= DCFL which is CFL

option(D) = True
L1∩L2∩L3 = RL ∩ DCFL ∩ REL = Recursively enumerable language(REL)
 Question 15
Let L = {ap| p is a prime}.
Then which of the following is true?
 A It is not accepted by a Turing Machine B It is regular but not context-free C It is context-free but not regular D It is neither regular nor context-free but accepted by a Turing Machine
Question 15 Explanation:
L = {ap | p is a prime}.
String generated by this language are L= { aaa,aaaaa,aaaaaaa,aaaaaaaaaaa,......},
and in L there is no definite pattern between the string .So this language is not regular language. and also not Context Free Language.
But this language is accepted by Turing machine using trial division algorithm
 Question 16
A FSM(finite state machine) can be considered to be a Turing machine of finite tape length
 A Without rewinding capability and unidirectional tape movement B Rewinding capability and unidirectional tape movement C Without rewinding capability and bidirectional tape movement D Rewinding capability and bidirectional tape movement
Question 16 Explanation:
Without rewinding capability and unidirectional tape movement.
• Rewind is a procedure in which  1st element of input go to last element on tape and process it and come back to starting of input tape.
• This is done by only Turing machine(TM's) because Turing machine can move in both direction so TM's is also called bidirectional.
• In Finite State Machine input move from left to right and one by one but It cannot be rewind. So FSM can be called as unidirectional tape movement
 Question 17
Let L = { w = (0+1)* | w has even number of 1’s }, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ?
 A (0*10*1)* B 0*(10*10*)* C 0*(10*1*)*0* D 0*1(10*1)10*
Question 17 Explanation:
L={w = (0 + 1)* | w has even number of 1's }
L Generating L is the set of all bit strings with even number of 1's.

Option(A) : False
This is not accepting string 110 (string 110 contains even number of 1's still not accepting)

Option(C) : False
This will accept some string which will not contain even number of 1's. example - 010, 1

Option (D) : False
This is not accepting string 11101 (String 11101 contains even number of 1's still not accepting)
 Question 18
Consider the following statements about the context-free grammar
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?
 A I only B I and III only C II and III only D I, II and III
Question 18 Explanation:
Statement I - True
G is ambiguous because string ab has multiple derivation trees like
S → SS → abS → ab
S → ab.
Example 2 : string ababab has multiple derivation trees like
S → SS → abS → abSS → ababS → ababab
S → SS → SSS → abSS → ababS → ababab

Statement II - False
G does not produce all strings with equal no. of a's and b's example : string ‘aabb’ cannot be generated by G

Statement III - True
The given grammar G generates the language (ab+ba)  which is Regular Language and therefore it is also DCFL
 Question 19
If L and L’ are recursively enumerable then L is
 A Regular B Context-free C Context Sensitive D Recursive
Question 19 Explanation:
If a language L and its complement L' are both recursively enumerable then both languages are recursive. if L is recursive, then L' is also recursive and consequently both recursively enumerable Question 20
S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of
 A All palindromes B All odd length palindromes C Strings that begin and end with the same symbol D All even length palindromes
Question 20 Explanation:
The language generated by the grammar is L= { a,b,aba,aaa,bbb,bab,aabaa, ......... }
All this strings in the language L are odd length palindromes
 Question 21
What is the highest type number that can be assigned to the following grammar?
S → Aa
A → Ba
B → abc
 A Type 0 B Type 1 C Type 2 D Type 3
Question 21 Explanation:
Given grammar is regular grammer(Type3) so it belongs to Type 0,Type 1,Type 2 as well. In the questions they are asking about highest type number Question 22
A problem whose language is recursive is called?
 A Unified problem B Boolean function C Recursive problem D Decidable
Question 22 Explanation:
→Recursive languages are Turing Decidable
→Recursively Enumerable languages are also called as (Recognizable, partially decidable, semi-decidable , Turing-acceptable or Turing-recognizable)
Note :
→Recursive languages are also called decidable.
→a Turing machine that halts for every given input
 Question 23

Which of the following sentences can be generated by

S -> aS | bA

A -> d | cA

 A bccdd B abbcca C abcabc D abcd
Question 23 Explanation:
S→aS
S→abA
S→abcA
S→abcd
 Question 24
What are the final states of the DFA generated from the following NFA? A q0, q1, q2 B [q0, q1], [q0, q2], [ ] C Q0, [q1, q2] D [q0, q1], q2
Question 24 Explanation:
→ Initially "q2" is final state
→ From the diagram, q0 state is connected to q1 state and q1 state is connected to q2 state through epsilon transitions.
→ In additions to q2 state, q0 and q1 states are also the final states of the DFA.
 Question 25
The number of states required by a Finite State Machine, to simulate the behavior of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
 A M x 2n B 2m+n C 2mn D M+n
Question 25 Explanation:
→ Generally, Finite State Machine consists of 2x states for a given input x
→ A word is of "n bits" and we have "m" such words. So, Total number of bits = m*n.
→Total number of sates required by FSM are 2m*n
 Question 26
What is the number of steps required to derive the string ((() ()) ()) for the following grammar?
S → SS
S → (S)
S → ε
 A 10 B 15 C 12 D 16
Question 26 Explanation:
1. s → (s)
2. s → (ss)
3. s → (s(s))
4. s → (s())
5. s → ((s)())
6. s → ((ss)())
7. s → (((s)s)())
8. s → ((()s)())
9. s → ((()(s))())
10. s → ((()())())
 Question 27
How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | w {0,1} number of 0’s is divisible by 2 and number of 1’s is divisible by 5, respectively} ?
 A 7 B 9 C 10 D 11
Question 27 Explanation:
In General If number of 0's is divisible by 'm' and number of 1's is divisible by 'n'
then number of states = m*n

In the question Number 0's is divisible by 2 and Number of 1's is divisible by 5
So Total number of states = 2*5=10 states
 Question 28
The following Finite Automaton recognizes which of the given languages? A {1, 0}* {01} B {1, 0}* {1} C {1}{1, 0}* {1} D 1*0* {0, 1}
Question 28 Explanation:
Given DFA accepts all strings that ending with “01” . So the language should be (0+1)*01.
so only option(A) is correct

Method 2 :

Option(A): True
Ending with "01" {01,001,101,0001,0101,1001,1101,...} It accepts all strings.

Option(B): False
Ending with "1". {1,01,11,001,...}. The strings "1", "11" are not accepted by Finite automata.

Option(C): False
Starting and ending with "1". {11,101,111,...}. The string "11" is not accepted by Finite automata.

Option(D): False
The string "0"  is not accepted by Finite automata.
 Question 29
Consider the following Deterministic Finite Automaton. 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
 A 0 B 1 C 2 D 3
Question 29 Explanation:
Only 2 strings are possible with 2nd, 3rd, 6th and 7th bits are 1.They are
1) 01110110
2) 01110111
 Question 30
Consider the following grammar.
S → AB
A → a
A → BaB
B → bbA
Which of the following statements is FALSE?
 A The length of every string produced by this grammar is even B No string produced by this grammar has three consecutive a’s C The length of substring produced by B is always odd D No string produced by this grammar has four consecutive b’s
Question 30 Explanation:
option(A) : True
length of every string produced by this grammar is even
Example : abba

option(B) : True
String produced by this grammar has a maximum of 2 consecutive a’s.

option(C) : True

option(D) : False
string produced by this grammar has 4 consecutive b’s
Example : abbbbaabba
S → AB
S → aB
S → abbA
S → abbBaB
S → abbbbAabbA
S → abbbbaabba
 Question 31
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?
 A It may halt and accept the input B It may halt by changing the input C It may halt and reject the input D It may never halt
Question 31 Explanation:
Halting of Turing machine is an undecidable problem. There are several possible out come of Turing machine are.
1. It may halt and accept the input
2. It may halt and reject the input
3. It may never halt
Turing machine never halt by  changing the input.
 Question 32
Two finite state machines are said to be equivalent if they :
 A Have the same number of edges B Have the same number of states C Recognize the same set of tokens D Have the same number of states and edges
Question 32 Explanation:
• Having same number of edges and same number of states doesn’t mean that finite state machines are equivalent.
• Two finite state machines are said to be equivalent if they have the same input and output alphabets and if, starting from their respective initial states, they produce the same output for any input string.
 Question 33
 A Any string of odd number of a’s B Any string of odd number of b’s C Any string of even number of a’s and odd number of b’s D Any string of odd number of a’s and odd number of b’s
Question 33 Explanation:
option(A) = False
it not accepting string "aaa"

option(B) = False
it not accepting string "bbb"

option(C) = False
it not accepting string "aabb"

option(D) = True
The language accepted by given finite automata is
L = {ab, ba, aaab, ababab, bababa, ..............}
∴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 :

 A 0 B 1 C 1 or more D 2 or more
Question 34 Explanation:
→In General PDA has only 1 auxiliary memory.
→PDA behaves like a Turing machine when the number of auxiliary memory is 2 or more.
 Question 35
Pushdown automata can recognize language generated by
 A Only context free grammar B Only regular grammar C Context free grammar or regular grammar D Only context sensitive grammar
Question 35 Explanation:
→Turing Machine recognizes ALL languages
→Linear Bounded Automata = CSL , CFL , RL
→Push down automata = CFL , RL
→Finite Automata recognizes Regular Language(RL) only
 Question 36

Consider the following two Grammars :

G1 : S → SbS|a
G2 : S → aB|ab,  A → GAB|a, B → ABb|b

Which of the following option is correct ?

 A Only G1 is ambiguous B Only G2 is ambiguous C Both G1 and G2 are ambiguous D Both G1 and G2 are not ambiguous
Question 36 Explanation:
→ A grammar is said to be ambiguous if we can generate more than one parse for same given string.
→ Both G1 and G2 are ambiguous As both grammars have 2 derivations for same given string:
→ To generate string ababa using G1 grammar has 2 different parse trees possible
G1 : S → SbS | a

1)
S → SbS
S →SbSbS
S →ababa

2)
S → SbS
S →SbSbS
S →ababa

→ To generate string aababbb using G2 grammar has 2 different parse trees possible
G2 : S → aB | ab, A→AB | a,  B → ABb | b

1)
S → aB
S →aABb
S →aABBb
S →aABABbb
S →aababbb

2)
S → aB
S → aABb
S → aAABbb
S → aABABbb
S → aababbb
 Question 37

Context sensitive language can be recognized by a :

 A Finite state machine B Deterministic finite automata C Non-deterministic finite automata D Linear bounded automata
Question 37 Explanation:
FA = Regular Language = Regular Grammar
PDA = CFL = CFG
LBA = CSL = CSG
TM = REL = REG

So, Context sensitive language can be recognized by a  LBA
 Question 38

The set A = { 0n 1n 2n | n=1, 2, 3, ......... } is an example of a grammar that is :

 A Context sensitive B Context free C Regular D None of the above
Question 38 Explanation:
0 0 1 1 2 2 = Accepted
0 0 0 1 1 1 2 2 2 2  = Not accepted
→Given Grammar is number of 0’s followed by equal number of 1’s and then followed by equal number of 2’s.
→ This grammar is accepted by linear bound automata  By using LBA which can move backward and upward and check the number of 0’s ,1's and 2's.
→This grammar is Context Sensitive language.
 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 ?

 A Both S1 and S2 are correct B Both S1 and S2 are not correct C Only S1 is correct D Only S2 is correct
Question 39 Explanation:
Statement 1 = True
It is "Equivalence problem" for the Recursive Enumerable languages and It is Undecidable. So, No Algorithm Exist.

Statement 2 = True
It is  "Halting problem of TM". It is Undecidable and So, No Algorithm Exist.
 Question 40
Consider the following finite state automaton. The language accepted by this automaton is given by the regular. A ab*b* B a*b* C b*b D b*ab*
Question 40 Explanation:
you can eliminate option(B) and option(C) and option(A)
In option(A) not accepting "ba"
In option(B) not accepting "ba"
In option(C) three is no "a"
option(D) is correct all strings we can generate
 Question 41
Which of the following languages over the alphabet {0,1} is described by the given regular expression: (0+1)*1(0+1)*1?
 A The set of all strings containing the substrings 11 B The set of all string containing at most two 1’s C The set of all strings containing at least two 1’s D The set of all strings that begins and ends with only 0.
Question 41 Explanation:
Given key is option(C)
It may be typo in question
Consider this 110 all options are eliminated

for option(C) the questions should be like this
Set of all strings containing at least two 1’s = (0+1)*1(0+1)*1(0+1)*
 Question 42
The language {Wa Xb Ya+b | a,b >=1} is:
 A Regular B Context free but non regular C Context sensitive but non context free D Type 0 but non context sensitive
Question 42 Explanation:
Wa  Xb  Ya+b
Wa  Xb  Yb Ya
So first compare XY and then WY for this we require 1 stack so it is context free not regular
 Question 43
Identify the true statement from the given statements:
(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
 A Only (1) B (1) and (2) C (1),(2) and (3) D (2) and (3)
Question 43 Explanation:
Statement 1 : True
Statement 2 : True
Recursive language are  closed under complement
Statement 3 : False
CFLs are not closed under complement
 Question 44
In the given language L={ab,aa,baa}, __ number of strings are in L*
(1) baaaba
(2) aabaaaa
(3) baaabaaaabaa
(4) baaabaaa
 A (1) B (2) C (3) D (4)
Question 44 Explanation:
L = { ab, aa, baa }
Let S1 = ab , S2 = aa and S3 =baa
1.  baaaba   =   baa ab a → It is not in L*
2.  aabaaaa = aa baa aa → S2 S3 S2 → It is in L*
3.  baaabaaaabaa = baa ab aa aa baa → S3 S1 S2 S2 S3 → It is in L*
4.  baaabaaa = baa ab aa a → It is not in L*
therefore, 2 strings are in L*
Correct option is (B)
 Question 45
Context free grammar can be recognized by
 A Finite state automaton B 2-way linear bounded automata C Pushdown automata D Both (B) and (C)
 Question 46
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called
 A Decidable B Undecidable C Interpretive D Non-deterministic
Question 46 Explanation:
→If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable
→It means for a given input it will always Halt
 Question 47
Consider the following two languages:

L1 = {x | for some y with |y|=2|x|, xy ∈ L and L is regular language}
L2 = { x | for some y such that |x| = |y|, xy∈L and L is regular language}

Which one of the following is correct?

Code:
 A Both L1 and L2 are regular languages B Both L1 and L2 are not regular languages C Only L1 is regular language D Only L2 is regular language
Question 47 Explanation:
Both L1 and L2 are regular languages
Contribute you explanation with diagrams and sent that image to academyera.com@gmail.com
 Question 48
Regular expression (a|b)(a|b) denotes the set
 A {a,b,ab,aa} B {a,b,ba,bb} C {a,b} D {aa,ab,ba,bb}
Question 48 Explanation:
(a|b)(a|b)
={aa,ab,ba,bb}
Note : (a | b) means Either "a" or "b"
 Question 49
Two finite state machines are said to be equivalent if they
 A Have same number of states B Have same number of edges C Have same number of states and edges D Recognized same set of tokens
Question 49 Explanation:
 Question 50

Consider the following language:

L1 = { an+m bna| n,m ≥ 0}
L2 = { an+m bn+m an+m |n,m ≥ 0}

Which one of the following is correct?

Code:
 A Only L1 is Context Free Language B Both L1 and L2 are not Context Free Language C Only L1 is Context Free Language D Both L1 and L2 are Context Free Language
Question 50 Explanation:
L1 = { an+m bnam | n,m ≥ 0}
Written as L1 = { am an bnam | n,m ≥ 0}
(push a′s into stack  read b′s and pop a′s , when no b′s left on input and stack still contains a's, then  keep reading a′s in input and pop a′s , when no a's left in input , and stack is empty, then accepted).
So,L1 can implemented using PDA . So  L1 is CFL

L2 = { an+m bn+m an+m | n,m ≥ 0}
Written as L2 = { ax b ax | x>=0}
For every "b" we can pop a's came before "b" but for "a" which came after b we have nothing to pop in stack. So L2 can't be implemented using PDA
So L2 is not CFL
 Question 51
What is the complement of the language accepted by the NFA shown below? A ∅ B {∈} C a* D {a, ∈}
Question 51 Explanation:
The language being accepted is a+
So, The complement of the language  a+ is a− a+ = { ϵ }
 Question 52
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?
 A Neither L nor L' is RE B One of L and L' is RE but not recursive;The other is not RE C Both L and L' are RE but not recursive D Both L and L' are recursive
Question 52 Explanation:
If Both L and L' are Recursive enumerable then L must be recursive

Option(A) is Possible
if L is itself is NOT RE. Then L' will also not be RE.

Option(B) is Possible
Suppose there is a language such that Turing machine halts on the input. The given language is Recursive Enumerable  but not recursive and its complement is NOT RE.
RE not closed under complement

Option(C) is Not Possible
If Both L and L' are Recursive enumerable then L must be recursive

Option(D) is Possible
Recursive closed under complement if L is recursive
 Question 53
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
 A L1′ is recursive and L2′ is recursively enumer­able B L1′ is recursive and L2′ is not recursively enumerable C L1′ and L2′ are recursively enumerable D L1′ is recursively enumerable and L2′ is recursive
Question 53 Explanation:
Recursive Language are closed under complement
Recursive Enumerable Languages are not closed under complement
L1′ is recursive and L2′ is not recursively enumerable
If L1 is Recursive, then L1' is also Recursive because it closed under complement
IF L2 is RE then L2' is not RE because not closed under complement
 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:
 A Only (ii) and (iii) are undecidable problems B (i), (ii) and (iii) are undecidable problems C Only (i) and (ii) are undecidable problems D Only (i) and (iii) are undecidable problems
Question 54 Explanation:
1. Whether a finite state automation halts on all inputs. Decidable
2. Whether a given context-free language is regular. Undecidable [ Regularity is decidable till DCFL class]
3. A Turing machine computes the products of two numbers, UNDECIDABLE, Even though we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, Undecidable.
 Question 55
Which of the following problems are decidable?
1. Does a given program ever produce an output?
2. If L is a context-free language, then, is L' also context-free?
3. If L is a regular language, then, is L' also regular?
4. If L is a recursive language, then, is L' also recursive?
 A (a), (b), (c), (d) B (a), (b) C (b), (c), (d) D (c), (d)
Question 55 Explanation:
1.  This is Turing Machine Halting problem. So, it is undecidable.
2.  CFL are not closed under complement so complement of CFL may or may not be CFL  so it is undecidable.
3.  Regular languages are closed under complementation. So, it is decidable
4.  Recursive languages are closed under complementation. So, it is decidable
 Question 56
Which of the following statements is true?
 A If a language is context free it can always be accepted by a deterministic pushdown automaton B The union of two context free language is context free C The intersection of two context free language is context free D The complement of a context free language is context free
Question 56 Explanation:
Option(A) = False
A language can be CFL even if it is being accepted by Non-Deterministic PDA(N-PDA)
Example :  { wwr : w ∈ Σ* and wr is reverse of w }
Option(B) = True
CFL are closed under Union, Concatenation and Kleen star
Option(C) and Option(D) are False
CFL are not closed under intersection and complementation
 Question 57
The best example of language for defining the non regular languages is:
 A Languages for palindrome and prime B Languages for palindrome and Even-Even C Language for prime and Even-Even D Language for palindrome and factorial
Question 57 Explanation:
 Question 58
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?
 A A*b* B (a | b)* C (ab)​ * D (a | b*)
Question 58 Explanation:
(a | b)*  which is nothing but (a + b)*
Set of all strings of a’s and b’s of any length including the null string. So L = { ε, a, b, aa , ab , bb , ba,  aaa, bbbb, bababa…….}
 Question 59
Regarding power of recognition of language, which of the following is false?
 A Non deterministic finite-state automata are equivalent to deterministic finite-state automata B Non deterministic PDA are equivalent to Deterministic PDA C Nondeterministic turing machines are equivalent to deterministic PDA D Multi tape Turing machines are equivalent to single tape Turing machines
Question 59 Explanation:
Power(TM) > NPDA > DPDA.
NTM and DTM are having same power
NFA and DFA have same power

option(A) : True

option(B) : False
power(NPDA) > DPDA.

option(C) : False
Power(TM) > NPDA > DPDA.

option(D) : True
 Question 60
If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
 A L1.L2 B L1 ∩ L2 C L1 ∩ R D L1 U L2
Question 60 Explanation:
→Context free language(CFL) are closed under union, concatenation and Kleene closure but not closed under intersection and complement.
→L1 ∩ R is closed under CFL

Note:
Intersection of any language with Regular language is definitely closed
 Question 61
Given language L={a(2*m)c(4*n)dnbm | m,n>=0}. Find the best appropriate match to recognize L.
 A Finite automata B Pushdown automata C Non deterministic turing machine D Non deterministic PDA
Question 61 Explanation:
→ Language generated is {aaccccdb, aaaaccccccccddbb, ...........}
→ push a's and c's into stack and reading one d in input pop 4 c's at a time and while reading b pop 2 a's and when no d's left in input and stack is empty then it is accepted. For this we require 1 stack
→ you can implement using Push Down Automata  because it have 1 stack
 Question 62
Consider the problem of determining string ‘w’ is given some turing machine ‘M’ will it enter into some state ‘q’, where q belongs to set of all states in Turing machine M and sting w is not equal to empty string. Which among the following is correct for above statement?
 A Given problems is computable B Given problem is non computable C Given problem has finite state solution D Given problem is solved in polynomial time.
Question 62 Explanation:
→Given problem is equivalent to halting problem of TM
→So, it is undecidable it means we don't have any algorithm to solve this problem
 Question 63
The CFG S → aS|bS|a|b is equivalent to regular expression
 A (a+b) B (a+b)(a+b)* C (a+b)(a+b) D All of these
Question 63 Explanation:
→ S → aS|bS|a|b is equvalent to (a+b)(a+b)*
→ Eliminate option(A) Which is only 1 character of length 1 either "a" or "b"
→ Eliminate option(C) Which is produces only 2 characters of  length 2 like {aa,ab,bb,ba}
→ option(B) which produces strings of length which are greater then 2 also and it starts with either a or b followed by any number of a's or b's
 Question 64
If L be a language recognizable by a finite automation, then language from {L}={w such that w is prefix of v where v ∈ L}, is a
 A Regular language B Context free language C Context sensitive language D Recursive enumeration language
Question 64 Explanation:
Regular languages are closed under prefix and suffix operations
 Question 65
Which of the following statements is correct?
 A A={a​n​b​n​ |n= 0,1,2,3..} is regular language B Set B of all strings of equal number of a's and b's defines a regular language C L(A*B*) ∩ B gives the set A D None of these
Question 65 Explanation:
option(A) = False
A={a​n​b​n​ |n= 0,1,2,3..}  = DCFL not Regular

option(B) = False
Equal number of a's and b's which is again DCFL not regular

option(D) = False
L(A*B*) ∩ B gives the set B not set A
 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 :
 A Only (i) is correct B Both (i) and (ii) are correct C Only (ii) is correct D Neither (i) nor (ii) is correct
Question 66 Explanation:
Every possible string over a, b generated by L(r) not by L(s) and L(t)
So, L(r) is superset among L(s) and L(t)
L(s) is propersubset of L(r) and L(s) is propersubset of L(t)
∴ L(r) ⊇ L(s) ⊇ L(t)
Given key is 1 but it should be 4
 Question 67
Regular sets are closed under
 A Union B Concatenation C Kleene's closure D All of these
Question 67 Explanation:
Regular sets are closed under
→Union
→Concatenation
→Kleene's closure
 Question 68

Consider the language L given by

L = {2nk | k>0, and n is non-negative integer number}

The minimum number of states of finite automaton which accept the language L is

 A N B N+1 C 2n D N(n+1)/2
Question 68 Explanation: Question 69

Which of the following problem is decidable for recursive language (L) ?

 A Is L = ф ? B Is w∈L, where w is a string ? C Is L = R, where R is given regular set ? D Is L = Σ* ?
Question 69 Explanation:
1. Emptiness of Recursive Language → undecidable
2. Membership problem of Recursive language → Decidable
3. L=R  → Undecidable
4. L(G) = Σ* Completeness problem or Totality problem of RL → Undecidable
 Question 70

Consider R to be any regular language and L1 , L2 be any two context-free languages

Which one of the following is correct ?
 A B L1 - R is context free C L1' is context free D L1 ∩ L2 is context free
Question 70 Explanation:
• CFL are closed under union and difference with regular language.
• Where  CFL are  not closed under intersection  and complementation a
• Complement of CFL is recursive language .
• Regular Language is closed under complementation
• CFL is closed under Intersection with Regular Language
option(A) : False
Context free language are closed under union but not complementation
L1∪L2 is CFL but complement(L1∪L2) is not CFL always

option(B) : True
L1−R = L1 ∩ R' =L1 ∩ R Always True
Regular language are closed under complementation and intersection of CFG and Regular is CFG.

option(C) : False
CFL are not closed under complementation

option(D) : False
CFL are not closed under intersection
 Question 71
Can a DFA simulate NFA?
 A No B Yes C Sometimes D Depends on NFA
Question 71 Explanation:
→Every DFA is a special kind of NFA. Thus if a language L is recognized by a DFA D, then since D is a special NFA, L is also recognized by an NFA also
→You can convert any NFA to DFA So NFA and DFA are both equivalent in power
 Question 72
Palindromes can't be recognized by any Finite State Automata because
 A FSA cannot remember arbitrarily large amount of information B FSA cannot deterministically fix the midpoint C Even if the mid-Point is known an FSA cannot find whether the second half of the matches the first half D All of the above
Question 72 Explanation:
→FSA cannot remember arbitrarily large amount of information because FSA has finite memory
→FSA cannot deterministically fix the midpoint because not able to find midpoint in palindrome.
FSA has finite memory So, Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.
 Question 73
If L1 is CSL and L2 is regular language which of the following is false?
 A L1-L2 is not context free B L1 intersection L2 is context free C ~L1 is context free D Both (A) and (C)
Question 73 Explanation:
option(A) : False
L1-L2 can be written as L1 ∩ L2' = CSL
Regular languages are closed under complement
CSL are closed under intersection with regular
According to Chomsky hierarchy every CFL is CSL. So L1 ∩ L2' = CLF also

option(B) : True
L1 ∩ L2 = CFL
CSL are closed under intersection with regular languages
So L1 ∩ L2 = CSL
According to Chomsky hierarchy every CFL is CSL. L1 ∩ L2 = CLF also

option(C) : False
Every CSL compliment is not always CFL
CSL is closed under compliment
CFL is not closed under complement. So, complement of CFL may or may not be a CFL.
 Question 74
Which of the following is True ?.
 A Turing machine is a simple mathematical model of general purpose computer B Turing machine is more powerful than finite automata C Turing Machine can be simulated by a general purpose computer D All of these
Question 74 Explanation:
Turing machine is a simple mathematical model of general purpose computer - TRUE
Turing machine is more powerful than finite automata - TRUE
Turing Machine can be simulated by a general purpose computer - TRUE
All options are true none of the option is wrong
 Question 75
Given two DFA's M1 and M2. They are equivalent if:
 A M1 and M2 has the same number of states B M1 and M2 accepts the same language i.e L(M1)=L(M2) C M1 and M2 has the same number of final states D None of the above
Question 75 Explanation:
→Having same number of states and same number of final states doesn't mean that they are equivalent
→Two DFA's M1 and M2 over the same alphabet are equivalent if they accept the same language
i.e. L(M1)=L(M2)
 Question 76
(00+01+10)(0+1)* represents:
 A Strings not starting with 11 B Strings of odd length C Strings starting with 00 D Strings of even length
Question 76 Explanation:
Given RE
(00+01+10)(0+1)*
Given regular Expression can generate strings with any length(Even length string or odd Length sting) but string must start with 00 or 01 or 10
So Eliminate option(B),option(D) and option(C)
option(A) : correct
String starts with 00 or 01 or 10 not with 11
 Question 77
Let R1 and R2 be regular sets defined over the alphabet, then
 A R1 ∩ R2 is not regular B R1 ∪ R2 is not regular C Σ * – R1 is regular D R1 * is not regular
Question 77 Explanation:
Regular languages are closed under
1. Intersection (∩)
2. Union (∪)
3. Complement
4. Kleene Closure (*)
Σ* – R1 = Σ* ∩ R1’ = It is regular language because it is closed under complement
 Question 78
State whether TRUE or FALSE

(i) In NDFA, the transition function δ: Q × Σ → 2Q
(ii) NDFA does not permit empty string transitions
 A (i) False (ii) False B (i) True (ii) False C (i) False (ii) True D (i) True (ii) True
Question 78 Explanation: DFA : Empty string transitions are not seen in DFA.
NFA : NDFA permits empty string transitions.
 Question 79
According to the given language, which among the following expression does it corresponds to ?
Language L={x ɛ {0,1} | x is of length or less}
 A (0+1+0+1+0+1+0+1)4 B (0+1)4 C (01)4 D (0+1+ɛ)4
Question 79 Explanation:
So we need to Generate stings of length 4 or less : It means string upto length 4 i.e. length 0 or length 1 or length 2 or length 3 or length 4

(0+1+ε)4
=ε+(0+1)1+(0+1)2+(0+1)3+(0+1)4
=(ε+0+1)4
 Question 80
Let G be a grammar in CFG and Let W 1, W2 ɛ L(G) such that |W1|=|W2| then which of the following statement is TRUE ?
 A Any derivation of W1 has exactly the same number of steps as any derivation of W2 B Different derivation have different length C Some derivation of W1 may be shorter the derivation of W2 D None of the options
Question 80 Explanation:
Given
G be a CFG Grammar
W1 and W2 are 2 strings of same Length

Example :
X → Yd | dd
Y → a

∴ |W1| = |W2|
W1 needs 1 derivation X → dd
W2 needs 2 derivation X → Y → ad

Note : They clearly specified in the option some derivations may be
 Question 81
A regular expression is (a+b*c) is equivalent to :
 A Set of strings with either a or one or more occurences of b followed by c. B (b*c+a) C Set of strings with either a or zero or more occurence of b followed by c D Both (B) and (C)
Question 81 Explanation:
→ Given regular expression is set of strings with either a or zero or more occurrence of b followed by c.
→In option(A) they not specified about zero occurrence
 Question 82
Which of the following are undecidable?
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)
 A P2 only B P1 and P2 only C P2 and P3 only D P3 only
Question 82 Explanation:
→ P1 = Membership algorithm in CFL is Decidable
→ P2 = CFL intersection with Regular is Decidable.
→ P3 = No algorithms to check that CFG is ambiguous or not so it is Undecidable
→ P4= we can determine ε is in language or not in the language . If Start Symbol itself contain ε then we can say it belongs to language is Decidable

So only P3 is is Undecidable
 Question 83
Recursive enumerable language are not closed under___
 A Set difference B Complement C Both (A) and (B) D None of the options
Question 83 Explanation:
→Recursively Enumerable languages are not closed under complementation.
Proof : Atm is Recursively Enumerable but complement(Atm) is not Recursively Enumerable

→Recursively Enumerable languages are not closed under set difference
 Question 84
What is the meaning of regular expression  ∑* 001 ∑*?
 A Any string containing '1' as substring B Any string containing '01' as substring C Any string containing '011' as substring D All string containing '001' as substring
Question 84 Explanation:
→ ∑* means any string using the input alphabets ∑ of any length 0 or any length
→ Σ* 001 Σ* = All string containing '001' as substring
 Question 85
The grammar S→ aSb | bSa | SS | ɛ is :
 A Unambiguous CFG B Ambiguous CFG C Not a CFG D Deterministic CFG
Question 85 Explanation:
→ Given grammar is ambiguous because it can generate more than 1 parse tree for the string "ab"

Parse Tree 1 = ab
```             S
/      \
S        S
/ | \      |
a  s  b     €
|
€```

Parse Tree 2 = ab
```      S
/    \
S      S
/     / | \
€     a  s  b
|
€```
 Question 86
If any string of a language L can be effectively enumerator in a lexicographic by an enumerator in a lexicographic order then language L is___
 A Regular B Context free but not regular C Recursive but not necessarily context free D Recursively enumerable but not necessarily recursive
Question 86 Explanation:
→The strings of a language L can be effectively enumerated means a Turing machine exists for language L which will enumerate all valid strings of the language.
→ Given Language is Recursive Language
→If the string is in lexicographic order then Turing Machine will accept the string and halt in the final state. But, if the string is not lexicographic order then Turing Machine will reject the string and halt in non-final state.
→We can not construct PDA for language L. So, the given language is not context free.
→ Given L is Recursive but not necessarily Context Free
 Question 87
The collection of turing recognizable languages are closed under :
i. Union
ii. Intersection
iii. complement
iv. Concatenation
v. star closure
 A I only B Both i,iv C I,ii,iv and v D All of the options
Question 87 Explanation:
→ Recursively Enumerable(RE) also called as recognizable, partially decidable, semi-decidable, Turing-acceptable or Turing-recognizable
→ RE are not closed under complement
→ RE are closed under Union, Intersection, Concatenation, Star Closure.
 Question 88
Which of the following regular expression is equal to (r1+r2)*?
 A R1*r2* B (r1r2)* C R1*r2*+r1r2 D (r1*r2*)*
Question 88 Explanation:
Let r1=a and r2=b

(a+b)* ≈ (a*b*)* ≈ (a*+b*)* ≈ (a+b*)* ≈ (a*+b)* ≈ (b*a+a*b)* Question 89
Which of the following is true?
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
 A S1 B S2 C Both S1 and S2 D None of the options
Question 89 Explanation:
→Single-tape Turing Machine and Multi-tape Turing machine have same expressive power.
→Non Deterministic Turing Machine and Deterministic Turing Machine are equivalent in power.

only s2 is true
 Question 90
Which of the following correctly defines kleene closure?
 A It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) B It is the finite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) C It is the finite set of all possible strings of all possible lengths over Σ(input set) D It is the infinite set of all possible strings of all possible lengths over Σ(input set)
Question 90 Explanation: Question 91
Which of the following is TRUE?
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
 A Mealy and moore machine are language acceptors B Finite state automata is language translator C NPDA is more powerful than DPDA D Mealy machine is more powerful than moore machine
Question 91 Explanation:
option(C) is correct

→NPDA is more powerful than DPDA
Power(NPDA) > Power(PDA)
→NFA and DFA are both are equivalent in power
→Mealy and Moore machine have equal power.

→Mealy and Moore machines are not language acceptors. They produce output based on input and/or state using actions. They are categorized under Transducers. Language acceptors are separate classification under FSM.
 Question 92
The string 1101 does not belong to the set represented by:
 A (00+(11)*0) B 1(0+1)*101 C (10)*(01)*(00+11)* D 110*(0+1) E Both option(A) and option(C)
Question 92 Explanation:
→ option(A) you can not generate 1101
→ option(B) you can generate 1101
→In option(c) after 11, we can't have 01 and so 1101 can not generated 1101.
→ option(D) you can generate 1101
So option(A) and option(C) are both are correct
 Question 93
Let n is the length of string to test for membership, then the number of table entry in CYK algorithm is:
 A N(n+1) B N2 +1 C N2 -1 D N(n+1)/2
Question 93 Explanation:
→ The table entries in CYK algorithm is in the form of a triangular matrix.
→ If the length of the string is ‘n’ then the Total Number of Table Entry in CYK algorithm is (n(n+1))/2
→ CYK algorithm takes O(n) time to compute each entry in table so whole table takes O(n)3 time in worst case
 Question 94
Which of the following statement is true?
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
 A Deterministic Context free language are closed under complement B Deterministic Context free language are not closed under union C Deterministic Context free language are closed under intersection with regular set D All of the options
Question 94 Explanation:
→Deterministic Context free language are closed under complement - True
→Deterministic Context free language are not closed under union - True
→Deterministic Context free language are closed under intersection with regular set - True
 Question 95
Which machine is equally powerful in both deterministic and non deterministic form?
 A PDA B TM C LBA D None of the options
Question 95 Explanation:
→NPDA is more power full then PDA
→Deterministic Turing machine and Non-Deterministic Turing machine are equivalent in power
→NFA and DFA also have same equivalent in power
 Question 96
Which of the following is a correct hierarchical relationships of the following where
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?
 A L1,L2⊂ L3⊂ L4⊂ L5⊂ L6 B L1⊂L2⊂ L3 ⊂L4⊂ L5 ⊂L6 C L2⊂L1⊂ L3 ⊂L4⊂ L5⊂ L6 D L1⊂L2⊂ L3⊂ L4⊂ L6⊂ L5
Question 96 Explanation:
 Question 97
Which machine is equally powerful in both deterministic and nondeterministic form?
 A Pushdown automata B Turing machine C Linear Bounded Automata D None of the options
Question 97 Explanation:
 Question 98
Which of the following is equivalent regular expressions?
i.((01)*(10)*)*
ii.(10+01)*
iii.(01)*+(11)*
iv.(0*+(11)*+0*)*
 A I and ii B Ii and iii C Iii and iv D Iv and i
Question 98 Explanation:
((01)*(10)*)* is same as (a*b*)* , where a=01 and b=10
(a*b*)* = (a+b)* which is (01+10)*.
Both (i) and (ii) have same expression Question 99
Which of the definitions generates the same languages as L, where
L={ x​n​ y​n​ , n>=1 }
i.   E → xEy | xy
ii.  xy | x​+​ xyy​ +
iii. x​+​ y​+
 A I only B I and ii only C Ii and iii only D Ii only
Question 99 Explanation:
L={ x​n​ y​n​ , such that n>=1 }
when n=1, string would be "xy"
when n=2, string would be "xxyy"
when n=3, string would be "xxxyyy"

So given language is Equal number of x's followed by y's

Statement (I) : In Statement (I) we have restriction over the number of a's and b's both being equal.
Statement (II) and Statement (III) There is no restriction over the number of a's and b's . You can have any number of x and y.
 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?

 A L = {ab,bb,ba} B L = {aa,ab,ba,bb} C L = {ab,bb,aa} D L = {ab,ba,aa}
Question 100 Explanation:
All possible strings of length 2 over Σ = {a,b} = {aa,ab,ba,bb} = total 4 strings
option(B) contains all 4 strings
 Question 101
The automaton which allows transformation to a new state without consuming any input symbols:
 A NFA B DFA C NFA-ɛ / NFA-l D All of the above
Question 101 Explanation:
NFA-l or ε-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol. It may appear in almost all kinds of nondeterministic automaton in formal language theory, in particular:
1. Nondeterministic Turing machine
2. Nondeterministic pushdown automaton
3. Nondeterministic finite automaton
 Question 102
Complement of a DFA can be obtained by:
 A Making starting state as final state B Make final as a starting state C Make final states non-final and non final as final D None of the options
Question 102 Explanation:
→The complement of a DFA can be obtained by making the non-final states as final states and vice-versa.
→The language accepted by the complemented DFA L2 is the complement of the language L1.
 Question 103
Concatenation operation refers to which of the following set operations:
 A Union B Dot C Kleene D None of the options
Question 103 Explanation:
→Concatenation refer to Dot.
→Concatenation means Two operands(or strings) are said to be joining together
Example : AB = A•B = {xy : x ∈A & y ∈B}.
 Question 104
Which of the following statement is true?
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
 A Mealy and moore machine are language acceptors B Finite state automata is language translator C NPDA is more powerful than DPDA D Mealy machine is more powerful than moore machine
Question 104 Explanation:
 Question 105
If L1 and L2 are regular sets then intersection of these two will be:
 A Regular B Non regular C Recursive D Non Recursive
Question 105 Explanation:
Regular languages are also closed under intersection.
 Question 106
let P,Q,R be a regular expression over Z. If P does not contain null string, then R=Q+RP has a unique solution____
 A Q*P B QP* C Q*P* D (P*Q*)*
Question 106 Explanation:
Arden’s Theorem
→Arden’s Theorem is  used to convert a given DFA to its Regular Expression.
→Arden’s Theorem can be used to find a regular expression for both DFA and NFA.
→Let P and Q be two regular expressions over ∑. If P does not contain a null string ∈, then R = Q + RP has a unique solution i.e. R = QP*
 Question 107
A finite automaton accepts which type of language:
 A Type 0 B Type 1 C Type 2 D Type 3
 Question 108
(0+ɛ)(1+ɛ) represents:
 A {0,1,01,ɛ} B {0,1,ɛ} C {0,1,01,11,00,10,ɛ} D {0,1}
Question 108 Explanation:
(0+ɛ)(1+ɛ) = { ɛ,0,1,01 }
 Question 109
What is the relation between DFA and NFA on the basis of computational power?
 A DFA>NFA B NFA>DFA C Equals D Can't be said
Question 109 Explanation:
→NFA and DFA have same computational power
→BY default All DFA are NFA. You can convert given NFA to DFA so both NFA and DFA are Equivalent in power
 Question 110
How many DFA's exits with two states over input alphabet {0,1}?
 A 16 B 26 C 32 D 64
Question 110 Explanation:
→For n states
→ Number of DFA’s = 2n * n(2*n) = 22 * 2(2*2) = 64
 Question 111
Complement of (a+b)* will be:
 A Π B ∅ C A D B
Question 111 Explanation:
→Complement of (a+b)* = ∑* - (a+b)*  = ϕ  = { } means no element is present
→Power set of {Π } = {{},{Π}}
→Power set of {}= {Π}
 Question 112
Finite automata requires minimum__ number of stacks
 A 1 B 0 C 2 D None of the options
Question 112 Explanation:
→ Finite Automata = 0 stacks
→ Pushdown Automata is a finite automata with extra memory called stack = 1 stack
 Question 113
Which of the following expression results in zero?
 A (0+0+1)(0+0+1) B (0+0+0)(0+1+1) C (1+0+0)(1+1+1) D (0+1+0)(1+0+1)
Question 113 Explanation:
→ Check all the options
→ In option(B) : product with 0 gives results also 0
=(0+0+0)(0+1+1)
=(0+1+1) gives results as 0 or 1
=(0+0+0) gives results as 0
 Question 114
A language L for which there exists a TM,, 'T', that accepts every word in L and either rejects or loops for every word that is not in L, is said to be
 A Recursive B Recursively enumerable C NP-Hard D None of the above
Question 114 Explanation:
→ A language L for which there exists a TM, 'T', that accepts every word in L and either rejects or loops for every word that is not in L, is said to be Recursively Enumerable

→ Only difference between Recursively Enumerable and Recursive Language is
• Recursively Enumerable  may or may not Halt
• Recursive Language is always Halt
 Question 115
The logic of pumping lemma us a good example of
 A The pigeonhole principle B The divide and conquer technique C Recursion D Iteration
Question 115 Explanation:
→ The Pigeonhole Principle states that if n pigeons fly into m pigeonholes and n > m then at least one hole must contain two or more pigeons.

→ Finite state automaton can assume only a finite number of states and because there are infinitely many input sequences, by the pigeonhole principle, there must be at least one state to which the automaton returns over and over again. This is an essential feature of the automaton.
 Question 116

A DFA can be expressed as a 5 tuple(Q, Σ, δ, q0, F), where δ is the transition function defined as ___?

 A Δ: Σ → Q B Δ: Q x Q → Σ C Δ: Q → Q D Δ: Q x Σ → Q
Question 116 Explanation: 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?

 A (r)|(s) is a regular expression representing L(r)UL(s) B (r)|(s) is a regular expression representing (L(r))* or (L(s))* C (r)* is a regular expression representing (L(r))* D (r)(s) is regular expression representing L(r)L(s)
Question 117 Explanation:
option(A) : union
(r)|(s) is a regular expression representing L(r) U L(s)

option(C) : Kleene closure
(r)* is a regular expression representing (L(r))* ; ( L(r1*)=(L(r1))* )

option(D) : Concatenation
(r)(s) is regular expression representing L(r)L(s)
 Question 118
Which of the definitions generates the same languages as L, where
L={ x​ n​ y​ n​ , n>=1 }
i.   E → xEy | xy
ii.  xy | x​+​xyy​ +
iii.  x​ +​ y​ +
 A I only B I and ii only C Ii and iii only D Ii only
Question 118 Explanation:
 Question 119
For the context free grammar G:
```R →  XRX|S
S →  aTb|bTa
T →  XTX|X|ϵ
X →  a|b```
The strings which are not in L(G) are:
 A Ab,ba,aab B Abb,aabab C A,b,aa D A,b,ϵ
Question 119 Explanation:
→3 examples of strings in L(G) : (ab, ba, aab)
→3 examples of strings not in L(G) : (a, b, aa)

Given grammar starts with R → XRX | S you can't generate only a or only b or aa
 Question 120
Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non negative decimal values, does not include even values ?
 A 0*1​ +​ 0*1* B 0*1*0​ +​ 1* C 0*1*0*1​ + D 0+1*0*1*
Question 120 Explanation:
→ Any non-negative odd number Represented in binary form then LSB bit must be 1
→ Any non-negative Even number Represented in binary form then LSB bit must be 0
→ In option(C)  0*1*0*1+ ( +  indicate must have 1 in LSB.) So, this Language won't contain any even numbers
 Question 121
Which of the following statements is/are TRUE ?
(i) The grammar S → SS | a is ambiguous (where S is the start symbol).
(ii) The grammar S → 0S1 | 01S | ϵ is ambiguous (the special symbol ϵ 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 | ϵ
U → yT
generates a language consisting of the string yxxyy.
 A Only (i) and (ii) are TRUE B Only (i) and (iii) are TRUE C Only (ii) and (iii) are TRUE D All of (i), (ii) and (iii) are TRUE
Question 121 Explanation:
option(A) : S→SS | a
This is ambiguous grammar because generates more then 1 parse tree for same string "aaa"
Derivation 1 :
S→SS→Sa→SSa→Saa→aaa
Derivation 2 :
S→SS→aS→aSS→aaS→aaa

option(B) : S → 0S1 | 01S | ϵ
This is ambiguous grammar because generates more then 1 parse tree for same string "01"
Derivation 1 :
S→0S1→01
Derivation 2 :
S→01S→01

option(C) : yxxyy
S → U
U → yT
yT → yxSy
yxSy → yxTy
yxTy → yxxyy
 Question 122
Which of the following strings would match the regular expression : p+ [3 – 5]* [xyz] ?
I. p443y
II. p6y
III. 3xyz
IV. p35z
V. p353535x
VI. ppp5
 A I, III and VI only B IV, V and VI only C II, IV and V only D I, IV and V only
Question 122 Explanation:

p+[3-5]*[xyz] = p+(3+4+5)*(x+y+z)
All strings must start with character p followed by 3 or 4 or 5 either 0 occurrence or more occurrence and must end with either x or y or z

I. p443y   =  Valid
Il. p6y       = Invalid because 6 cannot used we can use only among (3,4,5).
IV. p35z   = Valid
V. p353535x  =Valid
Vl. ppp5  = Invalid  Strings must end with x or y or z.
 Question 123
The number of strings of length 4 that are generated by the regular expression (0​+​ 1​+ ​ | 2​+​ 3​+​ )*, where | is an alternation character and {+, *} are quantification characters, is:
 A 08 B 09 C 10 D 12
Question 123 Explanation:
Given
Regular expression (0​+​ 1​+ ​ | 2​+​ 3​+​ )*
Total Possible strings of length 4 are :
0001, 0111, 0011, 0101, 0123, 2323, 2333, 2223, 2233, 2301.
Total 10 strings are possible.
With 01 = 0111, 0011, 0001, 0101
With 23 = 2333, 2233, 2223, 2323
Using both 01 and 23 = 0123, 2301
 Question 124
Which of the following is FALSE?
 A The grammar S→aS|aSbS|∈, where S is the only non-terminal symbol, and ∈ is the null string, is ambiguous. B An unambiguous grammar has same leftmost and rightmost derivation. C An ambiguous grammar can never be LR(k) for any k. D Recursive descent parser is a top-down parser.
Question 124 Explanation:
option(A) : True
Consider the string "aab" having more then 1 parse tree
Derivation 1 :
S−>aS
S−>aaSbS
S−>aaϵbS
S−>aabϵ
S−>aab
Derivation 2 :
S−>aSbS
S−>aaSbS
S−>aaϵbS
S−>aabϵ
S−>aab

option(B) : False
An Unambiguous grammars have different Left Most Derivation and Right Most Derivation

option(C) : True

option(D) : True
 Question 125
The number of strings of length 4 that are generated by the regular expression
(0|∈)1​ +​ 2* (3|∈),
where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is :
 A 08 B 10 C 11 D 12
Question 125 Explanation:
Regular expression (0 | ∈) 1+2* (3 | ∈)
Possible strings of length 4 are :
0122, 0123, 1123, 0112, 0113, 1113, 0111, 1222, 1123, 1111, 1223, 1112;
Total 12 strings are possible
 Question 126
If all the production rules have single non-terminal symbol on the left side, the grammar defined is:
 A Context free grammar B Context sensitive grammar C Unrestricted grammar D Phrase grammar
Question 126 Explanation:
Grammar Production form
α → β
In CFG Left hand side of production can have only one variable.
|α | = 1.
Their is no restriction on β

Example
S → AB
A → a
B → b
 Question 127
The context-free languages are closed for :
(i) Intersection
(ii) Union
(iii) Complementation
(iv) Kleene Star
then
 A (i) and (iv) B (i) and (iii) C (ii) and (iv) D (ii) and (iii)
Question 127 Explanation:
Context free languages are closed under Union and Kleene star.
Context free languages are not closed under intersection and complement
 Question 128
Which sentence can be generated by
S → d/bA
A → d/ccA
 A Bccddd B Aabccd C Ababccd D Abbbd E None
Question 128 Explanation:
→  The terminals in the grammar are d,b and c. There is no terminal 'a' at all. so we can eliminate options B,C,D
→ option(A) is also not correct because it is generating string "bccccd"
S → bA
S → bccA
S → bccccA
S → bccccd

None of the option is correct
 Question 129
Regular expression a+b denotes the set :
 A {a} B {ε, a, b} C {a, b} D None of these
Question 129 Explanation:
→Regular expression a+b denote the set { a, b}
→Either "a" or "b"
 Question 130
Which of the following is not true ?
 A Power of deterministic automata is equivalent to power of non-deterministic automata. B Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata. C Power of deterministic turing machine is equivalent to power of non-deterministic turing machine. D All the above
Question 130 Explanation:
option(A) :  Power of deterministic automata is equivalent to power of non-deterministic automata. - True

option(B) : Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata. - False
-NPDA is more powerful then DPDA

option(C) : Power of deterministic Turing machine is equivalent to power of non-deterministic Turing machine. - True
 Question 131
Identify the language which is not context-free.
 A L = { wwR ǀ wε{0,1}* } B L = { a​ n​ b​ n​ ǀ n≥0 } C L = { ww ǀ wε{0,1}* } D L = { a​ n​ b​ m​ c​ m​ d​ n​ ǀ n,m ≥0 }
Question 131 Explanation:
option(A)
L = { wwR ǀ wε{0,1}* } - CFL
we can find mid-point in the expression even in a non-deterministic way

option(B)
L = { a​ n​ b​ n​ ǀ n≥0 } - CFL
push a’s and then we can pop a’s for each occurrence of b.

option(C)
L = { ww ǀ wε{0,1}* }  - CSL
we can't implement using PDA
One might think to draw a non-deterministic push down automaton, but it will not help as first symbol will be at bottom of the stack and when the second W starts, we will not be able to compare it with the bottom of stack.

option(D)
L = { a​ n​ b​ m​ c​ m​ d​ n​ ǀ n,m ≥0 } - CFL
we can implement using PDA push a's and b's on seeing one c pop one b in stack follow the same for d on seeing d pop a. finally input became empty and stack became empty then accepted
 Question 132
Which of the following is the most general phase-structured grammar ?
 A Regular B Context - Sensitive C Context free D None of these
Question 132 Explanation:
→The term Phrase Structure Grammar for more restricted grammars in the Chomsky hierarchy : context-sensitive grammars or context-free grammars.
→Phrase Structure Grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.
→The most general one in the given options is context sensitive because it covers the context free grammars.
 Question 133
Which activity is not included in the first pass of two pass assemblers ?
 A Build the symbol table B Construct the machine code C Separate mnemonic opcode and operand fields. D None of these
Question 133 Explanation: Question 134
Which of the regular expressions corresponds to this grammar ?
S →AB/AS, A→a/aA, B→b
 A aa*b​ + B aa*b C (ab)* D a(ab)*
Question 134 Explanation:
"b" will appear exactly once in the given grammar so strike off options A,C,D

option(B) : aa*b
starts with "a" followed by number of a's either 0 occurrence or more occurrence and ends with "b"

S → AB→ab
or
S→AB→aAb→aab
or
S→AB→aAb→aaAb→aaab
or
S→AS→AAS→AAAS  -----so on aa*b
 Question 135
Which of the following is the most general phase-structured grammar ?
 A Regular B Context-sensitive C Context free D Syntax tree
Question 135 Explanation:
 Question 136
Which of the following strings is in the language defined by grammar
S → 0A
A → 1A/0A/1
 A 01100 B 00101 C 10011 D 11111
Question 136 Explanation:
S → 0A
S → 00A
S → 001A
S → 0010A
S → 00101
option(B) is correct
 Question 137
The following Context-Free Grammar (CFG) :
S → aB | bA
A → a | as | bAA
B → b | bs | aBB
will generate
 A Odd numbers of a’s and odd numbers of b’s B Even numbers of a’s and even numbers of b’s C Equal numbers of a’s and b’s D Different numbers of a’s and b’s
Question 137 Explanation:
option(A) : False
it can generate "aabb" which is even number of a's and b's
S→aB
B→aaBB
B→aabb

option(A) : False
it can generate "ab" which is odd number of a's and b's
S→aB
B→ab

option(D) : False
It always generate equal number a's and b's
 Question 138
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?
 A Both L​ 1​ and L​ 2​ are regular languages B Both L​ 1​ and L​ 2​ are not regular languages C Only L​ 1​ is regular language D Only L​ 2​ is regular language
Question 138 Explanation:
 Question 139
The number of substrings that can be formed from string given by “a d e f b g h n m p” is
 A 10 B 45 C 56 D 55
Question 139 Explanation:
Given
a d e f b g h n m p ;
All are distinct
So N=10
Total Number of substrings can be found using the below formula :
N(N+1)/2 + 1 ( 1 is for epsilon)
=10(10+1)/2 +1
=10(11)/2+1
Number of substrings = 56
 Question 140
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?
 A Only L​ 1​ is Context Free Language B Both L​ 1​ and L​ 2​ are not Context Free Language C Only L​ 1​ is Context Free Language D Both L​ 1​ and L​ 2​ are Context Free Language
Question 140 Explanation:
 Question 141
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?
 A Only (ii) and (iii) are undecidable problems B (i), (ii) and (iii) are undecidable problems C Only (i) and (ii) are undecidable problems D Only (i) and (iii) are undecidable problems
Question 141 Explanation:
 Question 142
The context free grammar for the language L = { an bm ck | k = | n – m |, n ≥ 0, m ≥ 0, k ≥ 0 } is
 A S → S1S3, S1 → aS1c | S2| λ,S2 → aS2b|λ, S3 → aS3b| S4 | λ,S4 → bS4c|λ B S → S1S3, S1→ aS1S2c | λ,S2 → aS2b|λ, S3 → aS3b| S4 |λ,S4 → bS4c|λ C S → S1|S2, S1→ aS1S2c | λ,S2 → aS2b | λ, S3 → aS3b | S4 |λ,S4 → bS4c|λ D S → S1 | S3, S1→ aS1c|S2 | λ,S2 → aS2b | λ, S3 → a S3b| S4 | λ,S4 → bS4c | λ
Question 142 Explanation: Question 143
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)
 A Only (i) is correct B Both (i) and (ii) are correct C Only (ii) is correct D Neither (i) nor (ii) is correct
Question 143 Explanation:
 Question 144
Consider the language L given by
L = { 2nk | k > 0 , and n is non − negative integer number }
The minimum number of states of finite automaton which accept the language L is
 A N B N+1 C 2 n D N (n + 1 )/2
Question 144 Explanation: Question 145
Which of the following problem is decidable for Recursive language (L) ?
 A Is L = ф ? B Is w∈L, where w is a string ? C Is L=R, where R is given regular set ? D Is L = Σ* ?
Question 145 Explanation:
1. Emptiness of Recursive Language → undecidable
2. Membership problem of Recursive language → Decidable
3. L=R  → Undecidable
4. L(G) = Σ* Completeness problem or Totality problem of RL → Undecidable
 Question 146
Consider R to be any regular language and L​1​ , L​2​ be any two context-free languages Which one of the following is correct ?
 A B L1 - R is context free C L1' is context free D L1 ∩ L2 is context free
Question 146 Explanation:
 Question 147
The number of states in a minimal deterministic finite automaton corresponding to the language L = { an | n≥4 } is
 A 3 B 4 C 5 D 6
Question 147 Explanation: Question 148
Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is
 A (1 + 010)* B (01 + 10)* C (1 + 010)* (0 + λ) D (1 + 01)* (0 + λ)
Question 148 Explanation:
option (a) : False
We can generate 010010 which contains pair of consecutive zeros

option (b) : False
We can generate 1001 which contains pair of consecutive zeros

option (c) : False
We can generate 0100 which contains pair of consecutive zeros

option (D) : True
Not contains any pair of consecutive zeros
 Question 149
Consider the following two languages :
L1 = {an bl ak | n + l + k>5 }
L2 = {an bl ak | n>5, l >3, k≤ l }
Which of the following is true ?
 A L1 is regular language and L2 is not regular language. B Both L1 and L2 are regular languages. C Both L1 and L2 are not regular languages. D L1 is not regular language and L2 is regular language
Question 149 Explanation:
→To implement L1 we don't need any stack so it regular language
→To implement L2 we need stack to remember the value of l (number of b's) so that it can be compared with k. so it not regular language
L1 is regular language and L2 is not regular language
 Question 150
LL grammar for the languageL = {an bm cn+m | m≥0, n≥0} is
 A S → aSc | S1 ; S1 → bS1c | λ B S → aSc | S1| λ ; S1 → bS1c C S → aSc | S1| λ ; S1 → bS1c| λ D S → aSc | λ ; S1 → bS1c| λ|
Question 150 Explanation:
option (A) : False
It is n > 0 and m >0 in every condition so m=0 is not satisfied

option (B) : False
It does not have any stopping condition. There is no way to stop the cycle S1→bS1c

option (C) : True
It can generate all strings by the language L

option (D) : False
State S1 is unreachable
 Question 151
Assume the statements S1 and S2 given as :

S1 : Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.
S2 : There exists an algorithm to determine whether two context free grammars generate the same language.

Which of the following is true ?
 A S1 is correct and S2 is not correct. B Both S1 and S2 are correct. C Both S1 and S2 are not correct. D S1 is not correct and S2 is correct.
Question 151 Explanation:
S1 : Finiteness problem of CFG - Decidable
S2 : Equality problem of CFG(check equivalence of 2 CFL'S) - Undecidable
 Question 152
Two finite state machines are said to be equivalent if they :
 A Have the same number of edges B Have the same number of states C Recognize the same set of tokens D Have the same number of states and edges
Question 152 Explanation:
 Question 153
 A Any string of odd number of a’s B Any string of odd number of b’s C Any string of even number of a’s and odd number of b’s D Any string of odd number of a’s and odd number of b’s
Question 153 Explanation:
Language accepted by finite automata is any string of odd number of a's and odd number of b's
{ ab , ba, aaab ,bbba,ababab,abbb, aaabbb ....... }
 Question 154
A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :
 A 0 B 1 C 1 or more D 2 or more
Question 154 Explanation:
• FA = 0 stack
• FA + 1 stack = Push Down Automata(PDA)
• FA + 2 stack = Turing Machines
• PDA + 1 stack = Turing Machines
 Question 155
Pushdown automata can recognize language generated by .
 A Only context free grammar B Only regular grammar C Context free grammar or regular grammar D Only context sensitive grammar
Question 155 Explanation:
 Question 156
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :
 A 2n−1 B 2n C N+1 D N​ 2
Question 156 Explanation:
A context free grammar  is in Chomsky Normal Form (CNF) if all production rules satisfy one of the following conditions:
A→BC or
A→a or
S→ε

Where S is start symbol and A,B and C are nonterminal symbols, a is a terminal symbol
neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the context-free grammar G.

In CNF at every step only 1 terminal can replace a variable, for example
S−AB
A−a
B−c

For generating string 'ac' 3 productions will be used.
S→AB
S→aB
S→ac.

The number of productions to be used in CNF : 2n – 1

Note:
Language does not include empty string(S→ε ), then it is CRF (Chomsky reduced form).
 Question 157
Context sensitive language can be recognized by a :
 A Finite state machine B Deterministic finite automata C Non-deterministic finite automata D Linear bounded automata
Question 157 Explanation:
Context sensitive language can be recognized by a Linear bounded automata
 Question 158
The set A={ 0​n​ 1​n​ 2​n​ | n=1, 2, 3, ......... } is an example of a grammar that is :
 A Context sensitive B Context free C Regular D None of the above
Question 158 Explanation:
 Question 159
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 ?
 A Both S1 and S2 are correct B Both S1 and S2 are not correct C Only S1 is correct D Only S2 is correct
Question 159 Explanation:
 Question 160
The ‘C’ language is
 A Context free language B Context sensitive language C Regular language D None of the above
Question 160 Explanation:
C and C++ both are context sensitive languages(CSL).
 Question 161
Let L be a set accepted by a nondeterministic finite automaton. The number of states in non-deterministic finite automaton is |Q|. The maximum number of states in equivalent finite automaton that accepts L is
 A |Q| B 2|Q| C 2|Q| – 1 D 2^|Q|
Question 161 Explanation:
If a problem can be solved with n state in NFA then in worst case number of states in the resulting DFA is 2n
Thus Given number of states in NFA = |Q|
After converting from NFA to DFA
Maximum number of states in equivalent DFA = 2|Q|
 Question 162
The context free grammar for the language L = {an bm | n ≤ m + 3, n ≥ 0, m ≥ 0} is
 A S → aaa A; A → aAb | B,B → Bb | λ B S → aaaA|λ, A → aAb | B,B → Bb | λ C S → aaaA | aa A | λ, A → aAb | B,B → Bb| λ D S → aaaA | aa A | aA | λ, A →aAb | B, B → Bb | λ
Question 162 Explanation:
When m =0 then n can be 0, 1,2,3 because of the given condition n<=m+3
So Such strings are λ, a, aa, aaa

option(A) : False
It can't generate the string  "a, aa"

option(A) : False
It can't generate the string  "a, aa"

option(A) : False
It can't generate the string   "a"

option(D) : True
It can generate all strings in the Language L
 Question 163
Given the following statements :
S1 : If L is a regular language then the language {uv | u ∈ L, v ∈ LR} is also regular.
S2 : L = {wwR} is regular language. Which of the following is true ?
 A S1 is not correct and S2 is not correct. B S1 is not correct and S2 is correct. C S1 is correct and S2 is not correct. D S1 is correct and S2 is correct.
Question 163 Explanation:
Given statement 1 can be written as LLR : S1 is Correct
• If L is regular Language then reversal of L(LR) is also regular Language. Regular Language are closed under Reversal operation . Hence u and v are Regular language
• Regular Languages are closed under Concatenation operation
• Therefore UV is Regular Language
Given statement 2 is CFL not Regular Language : S2 is Incorrect
• In order to find WW "W" need to be remember to match with "WR"
• Since Finite Automata don't have any memory so we cant implement using FA but we can implement using NPDA
• NPDA because it have 1 stack able to remember W
 Question 164
Consider the following statements :

(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 ?
 A I only B I and II C I and III D II and III
Question 164 Explanation:
→Recursive languages are closed under complementation, union, intersection...etc. Except Homomorphism and substitution(ε-free)
→Recursively enumerable languages are closed under union, intersection, concatenation ......etc. Except Complementation  and Set-difference
 Question 165
Which one of the following statement is false ?
 A Context-free languages are closed under union. B Context-free languages are closed under concatenation. C Context-free languages are closed under intersection. D Context-free languages are closed under Kleene closure
Question 165 Explanation:
→CFL are not closed under Intersection, Complementation, Set-difference Question 166
Pick the correct statements The logic of Pumping lemma is a good example of
 A The Pigeon-hole principle B The divide and conquer technique C Recursion D Iteration
Question 166 Explanation:
 Question 167
Any string of terminals that can be generated by the following CFG
S ⟶ XY
X ⟶ aX | bX | a
Y ⟶ Ya | Yb |a
 A Has at least one b B Should end in an ‘a’ C Has no consecutive a’s or b’s D Has at least two a’s
Question 167 Explanation:
option(A) : False
S ⟶ XY⟶ aY⟶ aa
No b in "aa"

option(B) : False
S ⟶ XY⟶ aY⟶ aYb⟶ aab
Ends with b Not end's with a

option(C) : False
S ⟶ XY⟶ aY⟶ aYb⟶ aab
"aab" consecutive a's

option(D) : True
Language generated by this grammar ={aa,aab,aaa...}
contains  at least 2 a's
 Question 168
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
 A A*b B A*baa* C A*ba* D None of the above
Question 168 Explanation:
length 1 in L1 = {}
length 2 in L1 = {ba}
length 3 in L1 = {aba,baa}.
length 4 in L1 = {abaa,aaba,baaa}.
L1={a*baa*}={ba,aba,abaa,abaaa*,aa*baaa*,a*ba*a.....}

length 1 in L2 = {a}.
length 2 in L2 = {ab}.
length 3 in L2 = {abb}.
length 4 in L2 = {abbb}.
L2={ab*}={a,ab,abbb,abb*...}

L1/L2={x: xy belongs to L1 for some y belongs to L2}

L1={a*baa*}={ba,aba,abaa,abaaa*,aa*baaa*,a*ba*a.....}
L2={ab*}={a,ab,abb*...}
L1/L2=a*ba* ={b,ab,aba,abaa,a*baa....}

option(C) is correct
 Question 169
Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below : The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
 A 5 B 4 C 3 D 2
Question 169 Explanation: The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is 4
 Question 170
An FSM can be a
 A Of finite tape length, rewinding capability and unidirectional tape movement. B Of finite tape length, without rewinding capability and unidirectional tape movement. C Of finite tape length, without rewinding capability and bidirectional tape movement. D Of finite tape length, rewinding capability and bidirectional tape movement.
Question 170 Explanation:
Finite State Automata can be
1. Finite tape length
2. Without rewinding capability
3. Unidirectional tape movement.
 Question 171
The major difference between a Moore and a Mealy machine is that
 A The output of the former depends on the present state and the current input B The output of the former depends only on the present state C The output of the former depends only on the current input D None of the above
Question 171 Explanation:
→Moore Machine Output depends only upon present state.
→In Moore Machine If input changes, output does not change.

→Mealy Machine Output depends on present state as well as present input.
→In Mealy Machine If input changes, output also changes.
 Question 172
“My Lafter Machin(MLM) recognizes the following strings :
(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)3x–1. ba
(iii) ab.(aab).3x–1.a
 A (ii) and (iii) are same, (i) is different. B (ii) and (iii) are not same. C (i), (ii) and (iii) are different. D (i), (ii) and (iii) are same.
Question 172 Explanation:
m is generating single "a".
If you observe clearly all of them above is generating (aba)x
This question is ambiguous, the wordings are not clear.
 Question 173
Which of the following is the most general phase structured grammar ?
 A Regular B Context-sensitive C Context free D None of the above
Question 173 Explanation:
 Question 174
Any syntactic construct that can be described by a regular expression can also be described by a :
 A Context sensitive grammar B Non context free grammar C Context free grammar D None of the above
Question 174 Explanation:
Any syntactic construct that can be described by Regular Expression can also be described by the Context free grammar.

Regular Expression
(a|b) (a|b|01)

Context free grammar
S → aA|bA
A → aA|bA|0A|1A|ε
 Question 175
Context-free Grammar (CFG) can be recognized by
 A Finite state automata B 2-way linear bounded automata C Pushdown automata D Both (B) and (C)
 Question 176
A context free grammar is :
 A Type 0 B Type 1 C Type 2 D Type 3
 Question 177
Consider a Moore machine M whose digraph is : Then L(M), the language accepted by the machine M, is the set of all strings having :
 A Two or more b’s. B Three or more b’s. C Two or more a’s. D Three or more a’s.
Question 177 Explanation:
→Minimum string that is accepted by the Moore machine M is "bb".
→So, The language contain 0 occurrence or more occurrence of a's and 2 or more occurrence of b's.
→So we can strike off options B,C,D
option(A) is correct
 Question 178
 A Set of all strings containing ‘ab’ B Set of all strings containing ‘aab’ C Set of all strings ending in ‘abab’ D None of the above
Question 178 Explanation:
→There is no final state in the given DFA so it won't accept anything
 Question 179
The regular expression given below describes :
r=(1+01)* (0+λ)
 A Set of all string not containing ‘11’ B Set of all string not containing ‘00’ C Set of all string containing ‘01’ D Set of all string ending in ‘0’
Question 179 Explanation:
option A: Incorrect
It can generate 11111 which contains 11

option B: Correct
No string contains contains "00"

option C: Incorrect
It can generate 11 so not all strings contains 01

option D : Incorrect
It can end with 01
 Question 180
Pumping lemma for regular language is generally used for proving :
 A Whether two given regular expressions are equivalent B A given grammar is ambiguous C A given grammar is regular D A given grammar is not regular
Question 180 Explanation:
Pumping lemma is used to prove a language is regular or not by  a proof by contradiction (of the language's regularity) may consist of exhibiting a word (of the required length) in the language that lacks the property outlined in the pumping lemma.
 Question 181
Which of the following problems is undecidable ?
 A To determine if two finite automata are equivalent B Membership problem for context free grammar C Finiteness problem for finite automata D Ambiguity problem for context free grammar
Question 181 Explanation:

Ambiguity problem for context free grammar is undecidable.

Decidable Problems
• 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.
• Membership problem for a context-free language is decidable because of CYK algorithm or any CFL parsing algorithm.
Undecidable Problems
• Ambiguity of context-free languages: Given a context-free 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 context-free languages: Given two context-free 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 182
Finite state machine can recognize language generated by __________.
 A Only context free grammar B Only context sensitive grammar C Only regular grammar D Any unambiguous grammar
Question 182 Explanation:
• Finite state machine can recognize language generated by regular grammar only.
• Pushdown automata can recognize language generated by Context free grammar or regular grammar.
• Context sensitive grammar generates Context sensitive language
• Context sensitive language can be recognized by a linear bounded automata.
 Question 183
The language L = {ai b ci │ i >= 0} over the alphabet {a, b, c} is:
 A A regular language. B Not a deterministic context free language but a context free language. C Recursive and is a deterministic context free language. D Not recursive.
Question 183 Explanation:
L = {ai b ci │ i >= 0} has only 1 comparison that can be done using a Deterministic PDA. Hence , its Deterministic CFL.

We can design a deterministic pushdown automata for the given language.
• For each occurrence of ‘a’ , we PUSH X in the stack.
• When ‘b’ appears, no stack operation is performed. But state of the automata is changed.
• For each occurrence of ‘c’ , we POP X from the stack.
• If at the end Z0 is on the stack top then input string is accepted
Context free languages are a proper subset of Recursive Languages.
∴ It is recursive too.
 Question 184
Which of the following statements is not correct?
 A Every recursive language is recursively enumerable. B L = {0n1n 0n │n=1, 2 , 3, ....} is recursively enumerable. C Recursive languages are closed under intersection. D Recursive languages are not closed under intersection.
Question 184 Explanation:
True : Every recursive language is recursively enumerable. True : L = {0n1n 0n │n=1, 2 , 3, ….} is recursively enumerable.
True : Recursive languages are closed under intersection.
False : Recursive languages are not closed under intersection
Recursive languages are closed under intersection
 Question 185
Context free grammar is not closed under:
 A Concatenation B Complementation C Kleene Star D Union
Question 185 Explanation:
Context-free languages are closed under union, concatenation and Kleene star
Context-free languages are not closed under intersection or complement. Question 186
Consider the following languages:
L1 = {am bn │ m ≠ n}
L2 = {am bn │ m = 2n+1}
L3 = {am bm │ m ≠ 2n}

Which one of the following statement is correct ?
 A Only L1 and L2 are context free languages B Only L1 and L3 are context free languages C Only L2 and L3 are context free languages D L1, L2 and L3 are context free languages
Question 186 Explanation:
Given,
L1 = {an bm m!=n }
show L11 = an bm n>m is context free and
show L12 = an bm  n <m is also context free
Then we know CFL are closed under union then L11 U L12 = {an bm m!=n } is also context free

Method 2 :
Given,
L1 = {an bm m!=n }
`L = {aab, abb, aaab, abbb, aaaab, aaabb, aabbb, abbbb ......}`

In each of the string, the number of a’s are followed by unequal number of b’s. Here, we need to maintain the order of a’s and b’s. That is, all the a’s are are coming first and then all the b’s are coming. Thus, we need a stack along with the state diagram. The count of a’s and b’s is maintained by the stack.

Approach used in the construction of PDA
As we want to design a NPDA, thus every time ‘a’ comes before ‘b’. When ‘a’ comes then push it in stack and if again ‘a’ comes then also push it. After that, when ‘b’ comes then pop one ‘a’ from the stack each time. So, at the end if the stack becomes empty and b is coming or string is end and stack is not empty then we can say that the string is accepted by the PDA. Given,
L2 = {an bm m=2n+1 }
L2 is CFL. We can rewrite it like {a2n+1 bn}={a2nabn}={aa2nbn} Given,
L3 = {an bm m!=2n } L1, L2 and L3 are context free languages
 Question 187
Which of the following are not regular?
(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 (A) and (B) only B (A), (B) and (C) only C (B), (C) and (D) only D (B) and (D) only
Question 187 Explanation:
option(A)Strings of even number of a's.
Regular

option(B)Strings of a's , whose length is a prime number.
This is not Regular but CSL

option(C)Set of all palindromes made up of a's and b's.
This is not Regular but CFL

option(D)strings of a's , whose length is a perfect square.
This is not Regular but CSL
 Question 188
Consider the languages L1 = φ and L2 = {1}. Which one of the following represents L1* ∪ L1* L2* ?
 A {∈} B {∈, 1} C Φ D 1*
Question 188 Explanation:
L1* U L1* L2*
L1 is the empty language.
L1* = Φ* which is {ε}. ie , the Kleene closure of the empty language gives the null string always.
We know that for any regular expression R,
R.ε=ε.R=R
L1* L2*
Φ* 1*
ε 1*  (L1* = Φ* which is {ε})
=1* (we know that 1.ε=ε.1=1)
L1* L2* =Φ* 1*=1*

Now Remaining part :
L1* U 1*
ε U 1*
We know that ε + R=R+ε =R
ε U 1*
=1*

Note :
R*+ϵ = ϵ+(ϵ+R)R* = ϵ+ϵR*+RR* = ϵ+R*+RR* = R*+(ϵ+RR*) = R*+R* = R*
option(D) : 1* is correct answer
 Question 189
Given the following statements :
(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?
 A Both (A) and (B) are false. B Both (A) and (B) are true. C (A) is true, (B) is false. D (A) is false, (B) is true.
Question 189 Explanation:
True : A class of languages that is closed under union and complementation has to be closed under intersection because regular language, context sensitive language(CSL) and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable(RE) language is closed under union but not under complementation but still it is closed under intersection.
False : A class of languages that is closed under union and intersection has to be closed under complementation. Question 190
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
 A LogK|W| ≤ h ≤ logK((|W|-1) / k-1) B LogK|W| ≤ h ≤ logK(K|W|) C LogK|W| ≤ h ≤ K logK|W| D LogK|W| ≤ h ≤ ((|W|-1) / k-1)
Question 190 Explanation:
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
LogK|W| ≤ h ≤ ((|W|-1) / k-1)

A fairly simple question involving some counting of leaves in a tree. The major purpose is to get students to think about derivation trees. To get the answer, establish a relation between the height of the derivation tree and the maximum number of leaves. For a tree of height h, the maximum number is hk. The other extreme is when there is only one node (i.e., there is only one variable in v). In this case, each level except the last has k − 1 leaves, so |w − 1| = h (k − 1).
 Question 191
Given the following two languages :
L1 = { an bn | n ≥ 0, n ≠ 100 }
L2 = { w ∈ {a, b, c}*| na(w) = nb(w) = nc(w) }
Which of the following options is correct ?
 A Both L1 and L2 are not context free language B Both L1 and L2 are context free language. C L1 is context free language, L2 is not context free language. D L1 is not context free language, L2 is context free language.
Question 191 Explanation: Question 192
Given the following two statements :
A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language.
Which of the following options is correct ?
 A Both (A) and (B) are false. B Both (A) and (B) are true. C (A) is true, (B) is false. D (A) is false, (B) is true.
Question 192 Explanation:
Both (A) and (B) are true.
L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language  Question 193
Which of the following pairs have different expressive power?
 A Single-tape-turing machine and multi-dimensional turing machine. B Multi-tape turing machine and multi-dimensional turing machine. C Deterministic pushdown automata and non-deterministic pushdown automata. D Deterministic finite automata and Non-deterministic finite automata
Question 193 Explanation:
1. Single Tape Turing machine and multi-dimensional Turing machine have same expressive power.
2. Multi Tape Turing machine and multi-dimensional Turing machine have same expressive power.
3. Deterministic push down automata and Non-deterministic push-down automata have different expressive power(NPDA is more expressive then DPDA)
• NDPDA can handle languages or grammars with ambiguity, but DPDA cannot handle languages with ambiguity and any context-free grammar
• NPDA cannot be converted into DPDA.
4. Deterministic finite automata and Non-deterministic finite automata have same expressive power.
• DFA and NFA are of same power because we can convert every NFA into DFA and and vice-versa
Hence, option (C) is correct answer.
 Question 194
Which of the following statements is false?
 A Every context-sensitive language is recursive. B The set of all languages that are not recursively enumerable is countable. C The family of recursively enumerable languages is closed under union. D The families of recursively enumerable and recursive languages are closed under reversal.
Question 194 Explanation:
option(A) : True
Every context-sensitive language is recursive.
According to Chomsky Hierarchy  Context Sensitive Languages are the subset of recursive languages option(B) : False
Theorem: Some languages are not recursively enumerable.
Proof: The set of strings is an infinite countable set.
The set of languages is not countable because it is the powerset of the set of strings.
Recursively enumerable languages are countable because TMs are countable.
Therefore, recursively enumerable languages all languages.

option(C) : True
The family of recursively enumerable languages is closed under union

option(D) : True
The families of recursively enumerable and recursive languages are closed under reversal Question 195
The regular expression for the complement of the language L = { anbm | n ≥ 4, m ≤ 3 } is:
 A (λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)* B (λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)* C (λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)* D (λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)*
Question 195 Explanation:
The complement of the language L = {anbm | n ≥ 4, m ≤ 3 } is L = {anbm|n < 4} U {anbm | m > 3}

option(A) : Using the term a*bbbb* it can accept a4b3 thus, it is not complemented

option(B) : Using (a+b)* ab (a+b)* it can accept a4b3 thus, it is not complemented

option(C) : Using (a+b)* ab (a+b)* it can accept a4b3 thus, it is not complemented

option(D) : (a+b)* ba (a+b)* cannot produce strings in an bm format and other 2 terms cannot produce any string an bm such that n>=4 and m<=3 and it produce produce any string an bm such that n < 4 and m > 3

 Question 196
Consider the following two languages :
L1 = {0i1j| gcd (i, j) = 1}
L2 is any subset of 0*.
Which of the following is correct ?
 A L1 is regular and L2* is not regular B L1 is not regular and L2* is regular C Both L1 and L2* are regular languages D Both L1 and L2* are not regular languages
Question 196 Explanation:
 Question 197
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes.
 A 2 B 4 C 5 D 6
 Question 198
Let L = {0n1n|n ≥ 0} be a context free language. Which of the following is correct ?
 A L’ is context free and Lk is not context free for any k ≥ 1. B L’ is not context free and Lk is not context free for any k ≥ 1. C Both L’ and Lk is for any k ≥ 1 are context free. D Both L’ and Lk is for any k ≥ 1 are not context free.
Question 198 Explanation:
Complement of L= {an bn : n ≥ 0} is L = {a, b}* - {an bn: n ≥ 0}
• So we look at how a string could fail to be in anbn
• There are 2 ways: either the a’s and b’s are out of order or there are not equal numbers of them. So our language L is the union of two other languages:
L1 = (a ∪ b)* - a*b* (strings where the a’s and b’s are out of order)
L2 = an bm n ≠ m (strings where the a’s and b’s are in order but there aren’t matching numbers of them)
L1 is context free. We gave a context-free grammar for it in class.
L2 is the complement of the regular language a*b*, so it is also regular and thus context free.

Since the union of two context-free languages is context free, L is context free
 Question 199
Given a Turing Machine
M = ({q0, q1, q2, q3}, {a, b}, {a, b, B}, δ, B, {q3})
Where δ is a transition function defined as
δ(q0, a) = (q1, a, R)
δ(q1, b) = (q2, b, R)
δ(q2, a) = (q2, a, R)
δ(q3, b) = (q3, b, R)
The language L(M) accepted by the Turing Machine is given as:
 A Aa*b B abab C aba*b D aba*
Question 199 Explanation:
Given transition,
δ(q0, a) = (q1, a, R)
δ(q1, b) = (q2, b, R)
δ(q2, a) = (q2, a, R)
δ(q3, b) = (q3, b, R)
From Given transition, We can build  DFA language L(M) accepted by the Turing machine is aba*b.
 Question 200
The regular grammar for the language L = {anbm | n + m is even} is given by
 A S → S1 | S2S1 → a S1| A1A1 → b A1| λ S2 → aaS2| A2 A2 → b A2| λ B S → S1 | S2S1 → a S1| aA1S2 → aaS2 | A2 A1 → b A1| λ A2 → b A2| λ C S → S1 | S2S1 → aaa S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ D S → S1 | S2S1 → aa S1 | A1S2 → aaS2 | aA2A1 → bbA1 | λA2 → bbA2 | b
Question 200 Explanation:

For n+m to be even There are two cases:
•  n and m are even: (aa)*(bb*)
•  n and m are odd: a(aa)*b(bb*)

Thus, a regular expression for the set {anbm : (n + m) is even} is (aa)*(bb*) +a(aa)*b(bb*).

option (A), option (B) and option (C) are not correct because it can generate sting like { aab, aaaab } which are odd

option(D) is correct answer it can generate strings like { \$,ab, aa,bb,abbb, aaab,aabb,aaab.......} which is even
• S→S1|S2
• S1→aaS1|A1 Hear A1 derives even number of b's  and S1 derives even number of a's
• S2→aaS2|aA2 Hear  A2 derives odd number of b's and aA2 will have even number of a's and b's
• A1→bbA1|λ→ Hear we get even number of b's
• A2→bbA2|b →Hear we get odd number of b's
 Question 201
Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is
 A {λ, a, b, ab, ba} ∪ {w∈{a, b}* | |w| > 3} B {a, b, ab, ba} ∪ {w∈{a, b}* | |w| > 3} C {w ∈ { a, b}* | |w| > 3} ∪ {a, b, ab, ba} D {λ, a, b, ab, ba} ∪ {w ∈ {a, b}* | |w| ≥ 3}
Question 201 Explanation:
Strings generated by language L = {aa, bb} which are even length.
Complement will be universal set of strings – {aa, bb}.
Lc = Σ* - L
Lc = Σ* - {aa, bb}
Lc = { λ, a, b, ab, ba } and strings { w{a, b}* | |w| ≥ 3 },
i.e. strings of length greater than or equal to 3.
 Question 202
Consider the following identities for regular expressions:
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true?
 A (a) and (b) only B (b) and (c) only C (c) and (a) only D (a), (b) and (c)
Question 202 Explanation:
Below all regular expressions are valid
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Any string constructed by LHS can also constructed by RHS and vice-versa
We can generate any strings by using (r + s)* which containing r or s or both or epsilon. and we can also construct DFA for (r + s)* which is same as (s + r)*. Question 203
Given the following two languages :
L1 = { uwwRν | u, v, w ∈ {a, b}+ }
L2 = { uwwRν | u, ν, w ∈ {a, b}+, |u| > |ν| }
Which of the following is correct ?
 A L1 is regular language and L2 is not regular language. B L1 is not regular language and L2 is regular language. C Both L1 and L2 are regular languages. D Both L1 and L2 are not regular languages.
Question 203 Explanation:
option(A) is the correct answer L1 is regular and L2 is non-regular.

L1 = {uwwRv : u, v, w ∈ {a, b}+}. L1 is regular. This may seem counterintuitive. But any string of length at least four with two consecutive symbols, not including the first and the last ones, is in L. We simply make everything up to the first of the two consecutive symbols u. The first of the two consecutive symbols is w. The second is wR. And the rest of the string is v. And only strings with at least one pair of consecutive symbols (not including the first and last) are in L because w must end with some symbol s. wR must start with that same symbol s. Thus the string will contain two consecutive occurrences of s. L is regular because it can be described the
Regular expression for L1 : r1= (a + b)+(aa + bb) (a + b)+

L2 = {uwwRν | u, ν, w ∈ {a, b}+, |u| > |ν|} ; L2 is not regular.
In Language L2 we need stack to compare length of u and v which can't be done by DFA.
So,L2 is not regular language
 Question 204
Given a Turing Machine
M = ({q0 , q1 }, {0, 1}, {0, 1, B}, δ, B, {q1 })
Where δ is a transition function defined as
δ(q0 , 0) = (q0 , 0, R)
δ(q0 , B) = (q1 , B, R)
The language L(M) accepted by Turing machine is given as :
 A 0* 1* B 00* C 10* D 1*0*
Question 204 Explanation:
Definition
what must happen when w ∈ Γ L (M). It says nothing about the outcome for any other input. When w is not in L (M), one of two things can happen: The machine can halt in a nonfinal state or it can enter an infinite loop and never halt. Any string for which M does not halt is by definition not in L(M).

Starting at the left end of the input, we read each symbol and check that it is a 0. If it is, we continue by moving right. If we reach a blank without encountering anything but 0, we terminate and accept the string. If the input contains a 1 anywhere, the string is not in L(00*), and we halt in a nonfinal state. To keep track of the computation, two internal states Q= {q0,q1}and one final state F= {q1} are sufficient. As transition function we can take As long as a 0 appears under the read-write head, the head will move to the right. If at any time a 1 is read, the machine will halt in the nonfinal state q0, since δ(q0,1) is undefined. Note that the Turing machine also halts in a final state if started in state q0 on a blank. We could interpret this as acceptance of λ, but for technical reasons the empty string is not included in above Definition.
δ(q0 , 0) = (q0 , 0, R)
δ(q0 , B) = (q1 , B, R)
 Question 205
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → ν, with |ν| = k > 1. The derivation tree for any string W ∈ L (G) has a height such that
 A H<((|W| - 1)/k-1) B Logk|W| < h C Logk|W| < h < ((|W| - 1)/k-1) D Logk|W| <= h <= ((|W| - 1)/k-1)
Question 205 Explanation:
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
LogK|W| ≤ h ≤ ((|W|-1) / k-1)

A fairly simple question involving some counting of leaves in a tree. The major purpose is to get students to think about derivation trees. To get the answer, establish a relation between the height of the derivation tree and the maximum number of leaves. For a tree of height h, the maximum number is hk. The other extreme is when there is only one node (i.e., there is only one variable in v). In this case, each level except the last has k − 1 leaves, so |w − 1| = h (k − 1).
 Question 206
The family of context sensitive languages is __________ under union and __________ under reversal.
 A Closed, not closed B Not closed, not closed C Closed, closed D Not closed, closed
Question 206 Explanation:
The family of context sensitive languages is closed under union and closed under reversal. Question 207
Match the following:
``` List - I                                     List - II

(a){an bn| n > 0} is a deterministic         (i)but not recursive language
context free language

(b)The complement of {an bn an| n > 0}       (ii)but not context free language
is a context free language

(c){an bn an} is context sensitive language  (iii)but can not be accepted by a
deterministic pushdown automation
(d)L is a recursive language                 (iv)but not regular``` A (a)-(i), (b)-(ii), (c)-(iii), (d)-(iv) B (a)-(i), (b)-(ii), (c)-(iv), (d)-(iii) C (a)-(iv), (b)-(iii), (c)-(ii), (d)-(i) D (a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
Question 207 Explanation:
1. anbn | n > 0 } is a deterministic context free language but not regular language
There exists at least one language that is CFL but not regular.
anbn | n > 0 } is a  context free language but not regular language
From this we can understand that regular languages are a proper subset of the context-free languages.
2. The complement of {anbnan| n > 0 } is context free language but not accepted by deterministic pushdown automata.
{anbnan| n > 0 } is not context free language but it's complement is Context free language and  we can implement by using NPDA. 3. {anbnan} is a context sensitive language but not context free language
4. L is a recursive language but not a context free language
Note : option(D) not clear. Excluded from evaluation
 Question 208
The language of all non-null strings of a’s can be defined by a context free grammar as follows :
S → aS|Sa|a
The word a3 can be generated by __________ different trees.
 A Two B Three C Four D Five
Question 208 Explanation:
a3 can be generated by four different trees. Question 209
The context free grammar given by
S → XYX
X → aX|bX|λ
Y → bbb
generates the language which is defined by regular expression:
 A (a + b)*bbb B Abbb(a + b)* C (a + b)*(bbb)(a + b)* D (a + b)(bbb)(a + b)*
Question 209 Explanation:
Given context free grammar
S → XYX
X → aX|bX|λ
Y → bbb
The equivalent RE for above grammar is: (a + b)*(bbb)(a + b)*
which is equivalent to Set of all string containing bbb as substring.

Trick :
X → aX|bX|λ  can generate (a + b)*
Y → bbb is generating bbb
hear "bbb" will be in the middle
So,
S → XYX
(a + b)* bbb (a + b)*
 Question 210
There are exactly __________ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
 A 64 B 56 C 1024 D 5832
Question 210 Explanation:
Let x be the number of states and y be the number of symbols
Therefore, x=3 and y=2
Number of different automata =  2x * xxy
=( 23 * 3(3*2) )
=23 * 36
=8*729
=5832
 Question 211
Given the following two languages:
L1 = {an b an | n > 0}
L2 = {an b an bn + 1 | n > 0}
Which of the following is correct ?
 A L1 is context free language and L2 is not context free language B L1 is not context free language and L2 is context free language C Both L1 and L2 are context free languages D Both L1 and L2 are not context free languages
Question 211 Explanation:
L1 = {an b an | n > 0}  which is CFL
push a′s into stack , do nothing with b , then pop all a′s from stack on reading a′s at the end there will be \$ in the bottom of stack and we will accept that string. we can implement this by using DPDA

L2 = {an b an bn + 1 | n > 0} which is not CFL but CSL
For L2, in addition to above comparison, we also need to ensure number of b's following the a's is just one more. This cannot be done with single stack. So, this makes L2 is not Context Free Language but we can implement using CSL

Option(A), L1 is context free and L2 is not context free language.
 Question 212
In case of Bus/Tree topology signal balancing issue is overcome by :
 A Strong Transmitter B Polling C Segmentation D Modulation
Question 212 Explanation:
Signal balancing is needed to limit the signal over certain limit; not too weak to attenuate across the medium before reaching far stations and not too strong to cause distortion, in both cases cannot be recovered.

This can be done within certain limit and also this limit the bus length. To increase the length of the LAN, the bus is split into segments joined by repeaters (transparent device); to overcome the impairments effects; in a non closed way.
 Question 213
Which of the following is True?
 A Turing machine is a simple mathematical model of general purpose computer B Turing machine is more powerful than finite automata C Turing Machine can be simulated by a general purpose computer D All of these
Question 213 Explanation:
True : Turing machine is a simple mathematical model of general purpose computer
A Turing machine is a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed

True :Turing machine is more powerful than finite automata
Let us take an example to show  Turing machine is more powerful than finite automata : A finite state machine can recognize a sequence that has three A's followed by three Bs e.g. AAABBB and so can a Turing machine. But only a Turning machine can recognize a sequence that has an arbitrary number of As followed by the same number of B's. That is a Turing machine is more powerful than a finite state machine because it can count.

True : Turing Machine can be simulated by a general purpose computer
Refer : https://arxiv.org/abs/1203.4667
There are 213 questions to complete.