## Theory-of-Computation

 Question 1
A language with string manipulation facilities uses the following operations. concat(sl, s2)- concatenates string s1 with s2. The output of concat(head(s), head(tail(tail(s)))), where s is acbc is
 A ab B ba C ac D as
Theory-of-Computation       Languages-and-Grammars       ISRO-2018
Question 1 Explanation:
 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
Theory-of-Computation       Regular-Language       ISRO-2018
Question 2 Explanation:
Option A: False: A = {an bn | n=1,2,3,…. } is Deterministic Context Free Language(DCFL) but not regular.
Option B: False: Equal number of a's and equal number of b's is also DCFL but not regular
Option C: False: L(A*B) ∩ B gives the set B but not set A.
L(A*B)= {AB+ AAB + …+AAAAB+B}
L(A*B)∩B=B
 Question 3
CFG (Context Free Grammar) is not closed under
 A Union B Complementation C Kleene star D Product
Theory-of-Computation       Context-Free-Language       ISRO-2018
Question 3 Explanation:
CFG (Context Free Grammar) is not closed under 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
Theory-of-Computation       Finite-Automata       ISRO-2018
Question 4 Explanation:
Let consider an example string:
Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111
---------------------------
1000 = I/p
----------------------------
It results 2's complement.
 Question 5
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
Theory-of-Computation       Context-Free-Language       ISRO-2018
Question 5 Explanation:
Explanation:
→ For CNF, it is 2x - 1
→ For GNF, it is x
 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
Theory-of-Computation       Context-Free-Language       ISRO CS 2008
Question 6 Explanation:
C is useless in S→ABCc so remove it.
S→ABc
Now see each of remaining production
Bb→bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
So
S→ABc→abc
 Question 7
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
Theory-of-Computation       Languages-and-Grammars       ISRO-2017 May
Question 7 Explanation:
According to the Chomsky hierarchy, both the statements are correct.

 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
Theory-of-Computation       Equivalence-of-Languages       ISRO-2017 May
Question 8 Explanation:
→ NPDA is more powerful than DPDA because
1. DPDA accept only a proper subset of CFL's ie. LL grammars.
2. NPDA can accept any CFL, which makes them more powerful over DPDA
3. Every NPDA can not be converted to an equivalent DPDA
 Question 9
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)*
Theory-of-Computation       Regular-Expression       ISRO-2017 May
Question 9 Explanation:
Option C is correct because it indicates L followed by (L + D)* where * means 0 or more occurences of L or D.
 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
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2017 May
Question 10 Explanation:
→ Recursively Enumerable problems are not closed under Complementation.
→ Set Difference A – B can be written as A ∩ B’ where B’ denotes complementation of B. So we can say that Recursively Enumerable problems are not closed under Set Difference
 Question 11
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
Theory-of-Computation       Regular-Expression       ISRO-2017 December
Question 11 Explanation:
→ Given expression denotes language that accepts set of all strings with even number of a’s followed by the odd number of b’s.
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
 Question 12
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
Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 12 Explanation:
Linear grammar means regular grammar which is in the form of A→ Ba | b (or) A→ aB|b
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of non-terminals
It is clearly seen that given grammar is not linear but context-free.
 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}
Theory-of-Computation       Languages-and-Grammars       ISRO-2017 December
Question 13 Explanation:
The language generated by given grammar is - L={b,bb,abb,abbb,ababb}
Hence it is ambn | n>m, m>=0
 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
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2017 December
Question 14 Explanation:
→ Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L1 ∩ L2 is a deterministic CFL.
→ Option B is false, as L3 is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.
→ Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L1 ∪ L2 is deterministic context free, hence it is also context free.
→ Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
 Question 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
Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 15 Explanation:
L = {ap | p is a prime}
L can only be accepted by a Turing machine
 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
Theory-of-Computation       Finite-Automata       ISRO-2016
Question 16 Explanation:
→ A FSM(finite state machine) can be considered to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
→ The finite state machine has less computational power than some other models of computation such as the Turing machine.
→ The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM's memory is limited by the number of states it has.
→ A finite state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite state machine is accepted by such a kind of restricted Turing machine, and vice versa.
 Question 17
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*
Theory-of-Computation       Regular-Expression       ISRO-2016
Question 17 Explanation:
→ The best way to find correct answer is option elimination method.
→ We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (Regular expression: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (Regular expression: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (Regular expression: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
 Question 18
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
Theory-of-Computation       Context-Free-Language       ISRO-2016
Question 18 Explanation:
Is ambiguous, as it has two parse tree for the string “abbaba”

G doesn’t produce all strings of an equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:

 Question 19
If L and L’ are recursively enumerable then L is
 A Regular B Context-free C Context Sensitive D Recursive
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2016
Question 19 Explanation:
→ If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
→ If L’ are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of L’ Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L.
→ This implies that L must be recursive.
 Question 20
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
Theory-of-Computation       Languages-and-Grammars       ISRO-2016
Question 20 Explanation:
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
 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
Theory-of-Computation       Languages-and-Grammars       ISRO-2016
Question 21 Explanation:
Grammar is belongs to Type 0 ,Type 1,Type 2,Type 3 because it is regular. Option D is right answer because they are asking only highest type number.
 Question 22
A problem whose language is recursive is called?
 A Unified problem B Boolean function C Recursive problem D Decidable
Theory-of-Computation       Resursive       ISRO CS 2011
Question 22 Explanation:
A formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise.
Recursive languages are also called decidable.
 Question 23

Which of the following sentences can be generated by

S -> aS | bA

A -> d | cA

 A bccdd B abbcca C abcabc D abcd
Theory-of-Computation       Context-free-language       ISRO CS 2011
Question 23 Explanation:
Given language:
S -> aS | bA
A -> d | cA
From the given productions, it is not possible to derive the sentence bccdd(two consecutive d’s).So option A is not correct.
In the string “abbcca”, there are two consecutive c’s followed by the letter ‘a’, This can’t be derived from the given productions,
From the given productions, it is also not possible to derive string which consists of the letter ‘c’ followed by ‘a’ , So the option (c ) also not correct
From given productions, we can generate the string “abcd”
 Question 24
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
Theory-of-Computation       DFA       ISRO CS 2013
Question 24 Explanation:
→An epsilon transition allows an automaton to change its state spontaneously, i.e. without consuming an input symbol.
→From the diagram, initially “q2” is final state.
→As there is epsilon transitions from qo to q1 and q1 to q2 and finally we reach the end state so q0,q1 are part of final states then q0,q1 and q2 are final states.
 Question 25
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
Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 25 Explanation:
A finite-state machine (FSM) an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition.
Generally FSM consists of 2x states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2mn.
 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
Theory-of-Computation       Languages-and-Grammars       ISRO CS 2014
Question 26 Explanation:
The required string consists of only only matched parenthesis enclosed with parentheses.
To generate the string ((() ()) ()) , we need to perform the steps sequentially.
As the string starts with left parentheses, we will start with the production S → (S).
Depending upon the string we will go for either left or right tree generation.
1) S → (S) // Replacing S by (S)
2) S → (SS) // Replacing by S by SS
3) S → ((S)S) //Replacing S by(S)
4) S → ((SS)S)// Replacing S by SS
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S)) [S → ε]
8) S → ((()(S))S) [S → ε]
9) S → ((()())S) [S → ε]
10) S → ((()()))
 Question 27
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
Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 27 Explanation:
From the given data
String which consists of 0’s and 1’s
Language is number of 0’s is divisible by 2 and number of 1’s is divisible by 5
Machine is minimum state deterministic finite automaton
The set of strings generated by {0,1} are ={ε,0,1,00,11,01,10,000,011,010 .. and so on}
The strings which are generated by language which is specified in the questions are
{ ε , 00, 11111, 0011111, 0011111 , 1111100, 1010111 , 000011111,….and so on }
So, strings accepted by the automaton have to be of length 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12….and so on, i.e. equation for length will be 2x + 5y (where x,y>=0 )
Number of 0’s divisible by 2 means , the possible remainders are 0 and 1 i.e; 2
Number of 1’s divisible by 5 means , the possible remainders are 4,3,2,1,0 i.e; 5
Total number of states are 2*5 =10
 Question 28
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}
Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 28 Explanation:
Given DFA accepts all string that ending with “01”, so the language should be (0+1)*01.
 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
Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 29 Explanation:
According to DFA transition diagram, the possible strings accepted by M is
01110110
01110111
Above two strings are are having constraint that 2nd, 3rd, 6th and 7th bits are 1. So, it satisfied above condition.
 Question 30
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
Theory-of-Computation       Languages-and-Grammars       ISRO CS 2014
Question 30 Explanation:
 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
Theory-of-Computation       Turing-machines       ISRO CS 2014
Question 31 Explanation:
→ The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.
→ Halting of Turing machine is an undecidable problem. A general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
→ Possible outcomes are
1. It may halt and accept the input.
2. It may halt and reject the input.
3. It may never halt.
 Question 32

Two finite state machines are said to be equivalent if they :

 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
Theory-of-Computation       Regular-Language       UGC-NET JUNE Paper-2
Question 32 Explanation:
We can call two finite state machines as equivalent if and only if the accept the same language.
 Question 33

The finite state machine given in figure below recognizes :

 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
Theory-of-Computation       Regular-Language       UGC-NET JUNE Paper-2
Question 33 Explanation:
The language accepted by above finite automata is:
L = {ab, ba, ababab, bababa, ..........}
Here, L is the language containing odd number of a’s and odd number of b’s.
 Question 34

A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

 A 0 B 1 C 1 or more D 2 or more
Theory-of-Computation       Context-Free-Language       UGC-NET JUNE Paper-2
Question 34 Explanation:
→ If we have two stacks then the stacks can act as a queue. Since a pushdown automata have a single stack as its memory device so if we have 1 more stack then the pushdown automata can be made to act as a turing machine.
→ So, total of 2 or more auxiliary memory are needed to make a pushdown automata behaves like a Turing machine.
 Question 35

Pushdown automata can recognize language generated by

 A Only context free grammar B Only regular grammar C Context free grammar or regular grammar D Only context sensitive grammar
Theory-of-Computation       Context-Free-Language       UGC-NET JUNE Paper-2
Question 35 Explanation:
Let A ➝ aA | ∈ ; Here A is a regular grammar which can be accepted by the pushdown automata.
B ➝ aBb | ab ; Here B is a Context free grammar which can be accepted by the pushdown automata.
 Question 36

Consider the following two Grammars :

G1 : S → 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
Theory-of-Computation       Context-Free-Language       UGC-NET JUNE Paper-2
Question 36 Explanation:
A grammar is said to be ambiguous if we get two different parse trees using either Leftmost derivation only or Rightmost derivation only.
To generate string “ababa” using G1 grammar the two different parse tree possible are:
 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
Theory-of-Computation       Turing-machines       UGC-NET JUNE Paper-2
Question 37 Explanation:
Context sensitive languages can be recognized by the Linear bounded automata.
L = {anbncn| where n>0}
is a context sensitive language and cannot be recognized by Finite state machine, Deterministic finite automata, Non-deterministic finite automata but L can be recognized by Linear Bounded Automata.
So, Context Sensitive Language can be recognized by Linear Bounded Automata.
 Question 38

The set A = { 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
Theory-of-Computation       Context-sensitive-language       UGC-NET JUNE Paper-2
Question 38 Explanation:
→ For above set we need infinite tape so this can’t be an example of Regular Grammar.
→ In case of Context Free grammar we have a stack only in which we can push 0’s as they come as input and can POP 0’s as 1’s come as input but when 2’s comes as input string we have NULL at the top of the stack so this Grammar can’t be a context free grammar.
→ Since in case of Context sensitive grammar we have linear bounded automata and a read/write head which can move backward and upward so this grammar can be accepted by Linear Bounded Automata. So, this grammar is a Context Sensitive Grammar.
 Question 39

Consider the following statements( ) :

S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.

Which of the following options is correct ?

 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
Theory-of-Computation       Turing-machines       UGC-NET JUNE Paper-2
Question 39 Explanation:
→ Checking if any two Turing machines M1 and M2 accept the same language or not is the equivalence problem. And equivalence problem of turing machines is Undecidable. So, Statement S1 is correct.
→ Halting problem of a turing machine is undecidable because if a turing machine accepts a string then it will halt but if a turing machine does not accept a string then it may or may not halt(can enter infinite loop). So, statement S2 is also correct.
 Question 40
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*
Theory-of-Computation       Nielit Scentist-B [02-12-2018]
Question 40 Explanation:
According to the given state transition diagram, the regular expression is
Step-1: Starting state has loop with symbol ‘b’ . It means, we can get n number of times ‘b’.
Step-2: The symbol ‘a’ between the starting state and end state. It means we can get only one
‘a’ after b*.
Step-3: The final state also having self loop with symbol ‘b’.
 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.
Theory-of-Computation       Nielit Scentist-B [02-12-2018]
Question 41 Explanation:
(0+1)* → We can take zero or many times
1→ definitely one should be there.
(0+1)* → We can take zero or many times
1→ definitely one should be there.
So, this regular expression containing at least two 1’s.
 Question 42
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
Theory-of-Computation       Nielit Scentist-B [02-12-2018]
Question 42 Explanation:
It is context free grammar but not regular because it requires to solve one stack of memory.
 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)
Theory-of-Computation       Nielit Scentist-B [02-12-2018]
Question 43 Explanation:
TRUE: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language
TRUE: The complement of a recursive language is recursive
FALSE because The complement of a deterministic context free language is deterministic context free.
 Question 44
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)
Theory-of-Computation       Nielit Scentist-B [02-12-2018]
Question 44 Explanation:
Any combination of strings in set {ab, aa, baa} will be in L*.
L = { ab, aa, baa }
Let S1 = ab , S2 = aa and S3 =baa
Option-1: baa ab a , We can’t partition with combinations of S1,S2 and S3.
Option-2: aa baa aa, We can’t partition with combinations of S1,S2 and S3.
Option-3: baa ab aa aa baa, We can partition this into S3S1S2S2S3
Option-4: baa ab aa a, We can’t partition with combinations of S1,S2 and S3.
We can’t partition the above options with combinations of {ab, aa, baa} except Option-3.
So the L* Consists of the string “baaabaaaabaa:
 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)
Theory-of-Computation       Context-Free-Language       Nielit Scientist-C 2016 march
Question 45 Explanation:
 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
Theory-of-Computation       Decidability-and-Undecidability       Nielit Scientist-C 2016 march
Question 46 Explanation:
● A decision problem is a function that associates with each input instance of the problem a truth value true or false.
● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.
● For simple machine models, such as finite automata or pushdown automata, many decision problems are solvable. In the case of deterministic finite automata, problems like equivalence can be solved even in polynomial time
 Question 47

Consider the following two languages:

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
Theory-of-Computation       Finite-Automata       UGC-NET DEC Paper-2
Question 47 Explanation:
if L is a regular language then we always have a string “w” which can be broken into “xy” such that |y| = 2|x|
Consider a language L= {a3n | n ≥ 0} , the strings in L are {ϵ, aaa, aaaaaa, …….}
then L1 = {an | n ≥ 0} as every string in L can be broken into three equal parts.
DFA for L:

DFA for L1:

By same logic L2 is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L1, since we can break only even length string into two equal parts such that |x| = |y| if “xy ∈ L”.
 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}
Theory-of-Computation       Regular-Expression       Nielit Scientist-C 2016 march
Question 48 Explanation:
● The Regular expression (a|b)(a|b) generates strings of length of 2.
● (a|b) means either a or b.
● The expression consists of two symbols of (a|b),which strings starting with either a or b and ending with 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
Theory-of-Computation       Finite-Automata       Nielit Scientist-C 2016 march
Question 49 Explanation:
Two automata M​ 0​ and M​ 1​ are said to be equivalent to each other if both accept exactly the same set of input strings.
 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
Theory-of-Computation       Context-Free-Language       UGC-NET DEC Paper-2
Question 50 Explanation:
→ L1 is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L1 so we can say L1 is a CFL.
→ L2 is not a context free language because L is equivalent to language = {apbpap | p ≥ 0}.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L2.
L2 is not a CFL.
 Question 51
What is the complement of the language accepted by the NFA shown below?
1.∅
2.{∈}
3.a*
4.{a, ∈}
 A 1 B 2 C 3 D 4
Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 22-07-2017
Question 51 Explanation:
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language 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
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       Nielit Scientist-B CS 22-07-2017
Question 52 Explanation:
If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.
 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
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       Nielit Scientist-B CS 22-07-2017
Question 53 Explanation:
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
 Question 54

Consider the following problems:

(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?

Which one of the following is correct?

Code:
 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
Theory-of-Computation       Decidability-and-Undecidability       UGC-NET DEC Paper-2
Question 54 Explanation:
• A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.
• Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable.
 Question 55
Which of the following problems are decidable?
1. Does a given ever produce an output?
2. If L is a context free language, then is L’ (complement of 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)
Theory-of-Computation       Nielit STA [02-12-2018]
Question 55 Explanation:
→ The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.
→ Context free languages are not closed under complement operation, so complement of CFL may or may not be CFL. Hence statement 2 is also undecidable.
→ Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.
→ Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
 Question 56
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
Theory-of-Computation       Nielit STA [02-12-2018]
Question 56 Explanation:
Context free languages closed under Union, concatenation and kleene star. But not close 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
Theory-of-Computation       Nielit STA [02-12-2018]
Question 57 Explanation:
Using the pumping lemma to show that a language is non-regular:
To show that L is not regular we need to do the following:
 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*)
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 2016 march
Question 58 Explanation:
It is clearly saying that all possible strings over the alphabet {a,b} is (a | b)*
 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
Theory-of-Computation       Equivalence-of-Languages       Nielit Scientist-B CS 2016 march
Question 59 Explanation:
→ NPDA is more powerful than DPDA.
→ NFA and DFA having same power.
→ NTM and DTM having same power.
→ Multi tape Turing machines are equivalent to single tape Turing machines
 Question 60
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
Theory-of-Computation       Context-Free-Language       Nielit Scientist-B CS 2016 march
Question 60 Explanation:
→ Intersection and complementation is not closed under context free languages(CFL).
→ L1 ∩ R is closed under CFL
→ L1.L2 and L1 U L2 is closed under CFL
 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
Theory-of-Computation       Nielit STA [02-12-2018]
Question 61 Explanation:
It generate the string is L={ aaccccdb, aaaaccccccccddbb….,}. So, it is push down automata. It require one stack memory.
 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.
Theory-of-Computation       Nielit STA [02-12-2018]
 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
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 2016 march
Question 63 Explanation:
● The option A gives either a or b expression which is of length of 1
● The option C gives aa,ab,ba or bb which are of length of 2
● But the CFG will produce strings, which of length of greater than 2 also.
● The option B gives string starts with either a or b followed by any number of a’s or b’s which is equivalent to CFG.
 Question 64
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
Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 2016 march
 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
Theory-of-Computation       Regular-Language       Nielit Scientist-B CS 2016 march
Question 65 Explanation:
Option-A is not regular language because it require one stack. If they given only an then it belongs to regular language.
Option-B, equal no of a's and equal no of b's is belongs to deterministic context free languages but not regular
Option-C is TRUE. If they given
L(A*B) ∩ B gives the set B but not set A.
L(A*B)= {AB+ AAB + …+AAAAB+B}
L(A*B)∩B=B
 Question 66

Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.

Consider the following:
(i)   L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)

Choose the correct answer from the code given below :

Code :
 A Only (i) is correct B Both (i) and (ii) are correct C Only (ii) is correct D Neither (i) nor (ii) is correct
Theory-of-Computation       Regular-Expression       UGC-NET DEC Paper-2
Question 66 Explanation:
L(s) = {∊, a, b, ab, bb, aa, ba, aab, baa,aaab, aaab,......}
L(r) = { ab, aab, aaab, aaaab, ………… }
L(t) = { b, ab, aab, aaab, aaaab, ……… }
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible string over a, b.
So L(s) ⊆ L(r) and L(t) ⊆ L(r).
L(r) can’t generate “b” but L(t) can’t.
So L(s) ⊆ L(t).
 Question 67
Regular sets are closed under
 A Union B Concatenation C Kleene's closure D All of these
Theory-of-Computation       Regular-Language       NieLit STA 2016 March 2016
Question 67 Explanation:
Regular sets are closed under union, concatenation and Kleene 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
Theory-of-Computation       Finite-Automata        UGC-NET DEC Paper-2
Question 68 Explanation:
n is a positive integer constant (means it is fixed)
assume n = 2 (for instance)
then we have : L = a2k | k>0
so k's value will be {1, 2, 3, 4, ........} and accordingly in L we have strings {a2, a4, a6, a8 .......}
→ It is clearly even number of a's (except zero a's) and for this we have 3 state DFA,
→ If n=3 then we will have a3, a6, a9 ..........
→ So, we require 4 states DFA
Hence answer will be "n+1" states are required.
 Question 69

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

 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 = Σ* ?
Theory-of-Computation       Decidability-and-Undecidability       UGC-NET DEC Paper-2
Question 69 Explanation:
→ A language is called Decidable or Recursive if there is a Turing machine which accepts and halts on every input string w.
→ Every decidable language is Turing-Acceptable.
→ For recursive language membership problem is decidable, i.e., a string “w” belongs to a recursive language “L” is decidable. Rest all are undecidable.
→ If language is recursive then it means , we have a Turing machine for the language which always halt. So when a string “w” is given to this turing machine it always halt either by accepting “w” or by rejecting “w”. Hence “Is w∈L” is decidable.
 Question 70

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

Which one of the following is correct ?

 A B C D
Theory-of-Computation       Regular-Language       UGC-NET DEC Paper-2
Question 70 Explanation:
Option 1: L1 and L2 are context free languages and context free languages are closed under union but not closed under complementation. It means intersection result may or may not br CFL. So when we will do subtraction the result may or may not be CFL.
Option 2: L1 is a CFL and R is a Regular language and if we do L1 - R the result will Regular language.
L1 = {an bn | n>0} is a context free language which can generate strings {ab, aabb, aaabbb, …….}
R = (a+b)* which can generate language {∈, a, b, aa, bb, ab, ba, …….}
So, L1 - R = {ф} which is a regular language.
And since every regular language is also a CFL so option 2 is correct.
Option 3: Context free languages are not closed under complementation. So option 3 is incorrect.
Option 4: Context free languages are not closed under Intersection. So option 4 is incorrect.
 Question 71
Can a DFA simulate NFA?
 A No B Yes C Sometimes D Depends on NFA
Theory-of-Computation       DFA       NieLit STA 2016 March 2016
Question 71 Explanation:
In terms of power, they are equivalent and there is an algorithm (subset construction) for converting an NFA to an equivalent DFA. As you might tell from the algorithm's name, it constructs subsets of states of the NFA. If your NFA has n states, the algorithm may output a DFA with 2​ n​ states but that's an upper bound. Sometimes, the number of states does not change at all or even reduces. So in practice, it matters less as to which one to use.
 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
Theory-of-Computation       Finite-Automata       Nielit Scientist-B CS 4-12-2016
Question 72 Explanation:
It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.
 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)
Theory-of-Computation       Closure-Property       Nielit Scientist-B CS 4-12-2016
 Question 74
Which of the following is wrong?
 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
Theory-of-Computation       Turing-machines       Nielit Scientist-B CS 4-12-2016
Question 74 Explanation:
● A Turing machine is a mathematical model of computation that defines an abstract machine,which 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.
● The machine operates on an infinite memory tape divided into discrete cells.
● The machine positions its head over a cell and "reads" (scans)the symbol there.
● Then, as per the symbol and its present place in a finite table of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allowing symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.
 Question 75
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
Theory-of-Computation       DFA       Nielit Scientist-B CS 4-12-2016
Question 75 Explanation:
Equivalence of two DFAs:
Two DFAs M1 and M2 over the same alphabet are equivalent if they accept the same language:
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
Theory-of-Computation       Regular-Expression       Nielit Scientist-B CS 4-12-2016
Question 76 Explanation:
From the expression we can generate strings with any length (even and odd).So option B and D are incorrect.
We can’t generate strings with only 00, we can generate strings starting with 00, 01 and 10 also, So option C is incorrect.
From the given expression (00+01+10)(0+1)*, we can’t generate strings with 11 , we can generate strings starting with 00, 01 and 10.
 Question 77
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
Theory-of-Computation       Regular-Language       ISRO CS 2015
Question 77 Explanation:
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleene-closure
Σ* - R1 is the complement of R1.
 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
Theory-of-Computation       DFA       JT(IT) 2018 PART-B Computer Science
Question 78 Explanation:
Formal Definition of an NDFA
An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where
Q is a finite set of states.
is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
DFA: Empty string transitions are not seen in DFA.
NDFA: permits empty string transitions.
 Question 79
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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 79 Explanation:
The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 80 Explanation:
Given data,
W1 and W2 are 2 strings,
|W1|=|W2| means same length
Example CFG grammar:
S→ Cbb | cc
C→ a
W1=cc W2=Cbb
As per the grammar, W1 require only one derivation S→ cc
W2 requires two derivations S→ Cbb→ abb
It means W1 is smaller than W2.
 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)
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 81 Explanation:
Given regular expression is (a+b*c). It means either a or zero or more occurence of b followed by c. But according to option A, they given “one or more occurences of b”. So, it is false.
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 82 Explanation:
Decidable Problems
A problem is decidable if we can construct a Turing machine which will halt in finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable problem has an algorithm to determine the answer for a given input.
Examples
Equivalence of two regular languages:Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.
Finiteness of regular language: Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.
Emptiness of context free language: Given a context free language, there is an algorithm whether CFL is empty or not.

Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.
Examples
Ambiguity of 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 83
Recursive enumerable language are not closed under___
 A Set difference B Complement C Both (A) and (B) D None of the options
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 83 Explanation:
→ Recursively enumerable languages are not closed under set difference or complementation.
→ The set difference L-P may or may not be recursively enumerable.
→ If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.
 Question 84
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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 84 Explanation:
∑* means it may be zero or any string. The above regular expression should contain 001.
 Question 85
The grammar S→ aSb | bSa | SS | ɛ is :
 A Unambiguous CFG B Ambiguous CFG C Not a CFG D Deterministic CFG
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 85 Explanation:

 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 86 Explanation:
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicographic order which is not accepted by TM. The give '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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 87 Explanation:
The collection of turing recognizable languages are closed under
1)Union
2)Intersection
3)Concatenation
4)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*)*
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 88 Explanation:
→ We can also get many number of r1 and many number of r2.
→ Given in regular expression to get together also many number of occurrences. So, correct answer is option D.
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 89 Explanation:
S1:In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing machine.so there expressing power is same
S2:Non-Deterministic TM is equivalent to DTM
 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)
Theory-of-Computation       Languages-and-Grammars       JT(IT) 2018 PART-B Computer Science
Question 90 Explanation:
Kleene closure
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
 Question 91
Which of the following is TRUE?
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 91 Explanation:
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
 Question 92
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)
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 92 Explanation:
Every 11 followed by 0 and no single occurrence of 1 is possible. So it cannot generate 1101 (or) 11011
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 93 Explanation:
→ CYK algorithm takes O(n) time to compute any one entry of the table by a method.
→ There are total n(n+1)/2 table entries, the whole table construction process takes O(n3) time in worst case.
 Question 94
Which of the following statement is true?
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 94 Explanation:
→ 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
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 95 Explanation:
→ NPDA is more powerful than DPDA because
1)DPDA accept only a proper subset of CFL's ie. LL grammars.
2)NPDA can accept any CFL, which makes them more powerful over DPDA
→ Deterministic TM is equal power to Non deterministic TM
 Question 96
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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 97 Explanation:
→ Deterministic turing machine and nondeterministic turing machine are same in terms of power.
→ NPDA is more powerful than DPDA.
 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
Theory-of-Computation       Nielit Scientist-B 17-12-2017
Question 98 Explanation:
→ The set of strings generated by the expression ((01)*(10)*)* are
{ε,01,10,0110,0101,1010,010110,01011010, ……}
→ The set of strings generated by the expression (10+01)* are
{ε,10,01,1010,0101,0110,101010,010101….}
→ The set of strings generated by the expression (01)*+(11)* are
{ε,01,11,0101,1111,010101,111111…}
→ The set of strings generated by the expression (0*+(11)*+0*)*are
{ε,0,11,00,000,011,110,0110,00110,01100,.....}
Compare the strings which are generated by option-1 and option-2.
 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​ +​ x yy​ +
iii. x​ +​ y​ +
 A i only B i and ii only C ii and iii only D ii only
Theory-of-Computation       Languages-and-Grammars       Nielit Scientific Assistance IT 15-10-2017
Question 99 Explanation:
The language L={ x​ n​ y​ n​ , n>=1 }
For n=1, xy
n=2,x​ 2​ y​ 2
n=3,x​ 3​ y​ 3
In the above language , there are equal number of x’s followed by y’s
Definition-1:E→ xEy |xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X​ +​ means one or more x’s
Y​ +​ means one or more y’s
Definition -2 :
The expression xy|x​ +​ x yy​ + ​ gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition -3 :
The expression x​ +​ y​ +​ gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition-3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
 Question 100

A language is a subset of Σ* for some alphabet Σ. If a language takes all possible strings of length 2 over Σ = {a,b}, then, which of the below is correct?

 A L = {ab,bb,ba} B L = {aa,ab,ba,bb} C L = {ab,bb,aa} D L = {ab,ba,aa}
Theory-of-Computation       Languages-and-Grammars       JT(IT) 2018 PART-B Computer Science
Question 100 Explanation:
→ All possible strings of length 2 over Σ = {a,b} = 4(aa,ab,ba,bb}.
→ We are computing all possible strings using 2n formula. Where n is number of 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
Theory-of-Computation       Nielit STA 17-12-2017
Question 101 Explanation:
→ NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

We extend the class of NFAs by allowing instantaneous (ε) transitions:
1. The automaton may be allowed to change its state without reading the input symbol.
2. In diagrams, such transitions are depicted by labeling the appropriate arcs with ε.
3. Note that this does not mean that ε has become an input symbol. On the contrary, we assume that the symbol ε does not belong to any alphabet.
 Question 102
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
Theory-of-Computation       Nielit STA 17-12-2017
Question 102 Explanation:
→ If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa. Note: If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method.
 Question 103
Concatenation operation refers to which of the following set operations:
 A Union B Dot C Kleene D none of the options
Theory-of-Computation       Nielit STA 17-12-2017
Question 103 Explanation:
→ It does not matter in which order we group the expression with the operators as they are associative.
→ If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.
 Question 104
Which of the following statement is true?
 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
Theory-of-Computation       Nielit STA 17-12-2017
Question 104 Explanation:
→ NPDA is more powerful than DPDA because
1.DPDA accept only a proper subset of CFL's ie. LL grammars.
2.NPDA can accept any CFL, which makes them more powerful over DPDA
 Question 105
If L1 and L2 are regular sets then intersection of these two will be:
 A Regular B Non regular C Recursive D Non Recursive
Theory-of-Computation       Nielit STA 17-12-2017
Question 105 Explanation:
If L1 and If L2 are two regular languages, their intersection L1 ∩ L2 will also be regular.
Example
L1= {am bn | n ≥ 0 and m ≥ 0} and L2= {am bn ∪ bn am | n ≥ 0 and m ≥ 0}
L3 = L1 ∩ L2 = {am bn | n ≥ 0 and m ≥ 0} is also regular.
 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*)*
Theory-of-Computation       Nielit STA 17-12-2017
Question 106 Explanation:
→ According to arden’s theorem, we can directly find the answer is QP*
→ In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the properties of regular expressions.
Statement:
Let P and Q be two regular expressions.
If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*
Proof:
R=Q+(Q+RP)P [After putting the value R=Q+RP]
=Q+QP+RPP
When we put the value of R recursively again and again, we get the following equation:
R=Q+QP+QP2+QP3…..
R=Q(ε+P+P2+P3+…. )
R=QP*[As P* represents (ε+P+P2+P3+….)]
 Question 107
A finite automaton accepts which type of language:
 A Type 0 B Type 1 C Type 2 D Type 3
Theory-of-Computation       Nielit STA 17-12-2017
Question 107 Explanation:

 Question 108
(0+ɛ)(1+ɛ) represents:
 A {0,1,01,ɛ} B {0,1,ɛ} C {0,1,01,11,00,10,ɛ} D {0,1}
Theory-of-Computation       Nielit STA 17-12-2017
Question 108 Explanation:
(0+ɛ)(1+ɛ) represents {0,1,ɛ}
 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
Theory-of-Computation       Nielit STA 17-12-2017
Question 109 Explanation:
Both NFA and DFA having same computational power, as both defines the same class of regular languages.
 Question 110
How many DFA's exits with two states over input alphabet {0,1}?
 A 16 B 26 C 32 D 64
Theory-of-Computation       Nielit STA 17-12-2017
Question 110 Explanation:
Number of DFA’s = 2n * n(2*n)
=22*24
=4*16
=64
 Question 111
Complement of (a+b)* will be:
 A π B ∅ C a D b
Theory-of-Computation       Nielit STA 17-12-2017
Question 111 Explanation:
Given expression accept all string so complement will accept nothing
 Question 112
Finite automata requires minimum__ number of stacks
 A 1 B 0 C 2 D none of the options
Theory-of-Computation       Nielit STA 17-12-2017
Question 112 Explanation:
Finite automata doesn’t require any stack operation
 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)
Theory-of-Computation       Regular-Expression       KVS 22-12-2018 Part-B
Question 113 Explanation:
→ The second option gives zero value.
→ (0+0+0) gives the value 0
→ (0+1+1) gives either 0 or 1.
→ (0+0+0)(0+1+1) gives ), as product of 0 with anything is 0
 Question 114
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
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       Nielit Scientific Assistance CS 15-10-2017
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
 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
Theory-of-Computation       Pumping Lemma       Nielit Scientific Assistance CS 15-10-2017
Question 115 Explanation:
→ The pigeonhole principle is nothing more than the obvious remark: if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy.
→ In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
 Question 116

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

 A δ: Σ → Q B δ: Q x Q → Σ C δ: Q → Q D δ: Q x Σ → Q
Theory-of-Computation       Finite-Automata       JT(IT) 2018 PART-B Computer Science
Question 116 Explanation:
Deterministic Finite Automata (DFA)
DFA consists of 5 tuples {Q, ∑, q, F, δ}.
Q : set of all states.
∑ : set of input symbols. (Symbols which machine takes as input)
q : Initial state. (Starting state of a machine)
F : set of final state.
δ : Transition Function, defined as δ: QX∑ → Q.
 Question 117

If r and s are regular expression representing the languages L(r) and L(s), respectively, then which of the following is FALSE?

 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)
Theory-of-Computation       Regular-Expression       JT(IT) 2018 PART-B Computer Science
Question 117 Explanation:
If r and s are regular expressions denoting the languages L(r) and L(s), then
1. Union : (r)|(s) is a regular expression denoting L(r) U L(s)
2. Concatenation : (r)(s) is a regular expression denoting L(r)L(s)
3. Kleene closure : (r)* is a regular expression denoting (L(r))*
(r) is a regular expression denoting L(r).
 Question 118
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​ +​ x yy​ +
iii. x​ +​ y​ +
 A i only B i and ii only C ii and iii only D ii only
Theory-of-Computation       Languages-and-Grammars       Nielit Scientific Assistance CS 15-10-2017
Question 118 Explanation:
The language L={ x​ n​ y​ n​ , n>=1 }
For n=1, xy
n=2,x​ 2​ y​ 2
n=3,x​ 3​ y​ 3
In the above language , there are equal number of x’s followed by y’s
Definition-1​ :E→ xEy |xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X​
+​
means one or more x’s
Y​
+
​ means one or more y’s
Definition -2 : The expression xy|x​ +​ x yy​ + ​ gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition -3 :
The expression x​ +​ y​ +​ gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition-3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
 Question 119

For the context free grammar G:

```R →  XRX|S,
S →  aTbTa,
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,ϵ
Theory-of-Computation       Languages-and-Grammars       JT(IT) 2016 PART-B Computer Science
Question 119 Explanation:
We can’t generate the strings “a” and “b” because the Starting symbol is R→ XRX|S.
 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*
Theory-of-Computation       Regular-Expression       UGC NET CS 2017 Nov- paper-2
Question 120 Explanation:
Binary numbers can easily find for odd numbers using LSB is 1 and even numbers LSB is 0. Option C won’t contain 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 | e is ambiguous (the special symbol e represents the empty string and S is the start symbol).
(iii) The grammar (where S is the start symbol).
S → T/U
T → x S y ? xy ? e
U → yT
generates a language consisting of the string yxxyy.
 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
Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Nov- paper-2
Question 121 Explanation:
Option (i) parse tree is ambiguous.

Option (ii): For producing string 01 it gives 2 parse tree. So, it is also ambiguous.
Option (iii): It is also true
 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
Theory-of-Computation       Regular-Expression       UGC NET CS 2017 Jan -paper-2
Question 122 Explanation:
This problem looks very difficult but solving procedure is very easy.
Given regular expression is p+[3-5]*[xyz]
[3-5]* means (3+4+5)* It can generate these numbers many number of times.
[xyz] → ends with either x or y or z or any combination but not violate order of occurrences
I. p443y → matched because it satisfied above regular expression.
Il. p6y → not matched because 6 not present in regular expression.
III. 3xyz → not matched because it not starts with p.
IV. p35z → matched because it satisfied above regular expression.
V. p353535x → matched because it satisfied above regular expression.
Vl. ppp5 → not matched because it is not end with x or y or z or any combination.
 Question 123
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
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 Aug- paper-2
Question 123 Explanation:
Consider a=0+1+ and b=2+3+
Hence (0+1+ | 2+3+)* = (0+1+ + 2+3+)* = (a+b)*
Now since the min string in 0+1+ is "01" hence "a" has min length two.
Similarly the min string in 2+3+ is "23" , hence "b"has min length two.
We require 4 length strings. + We can generate 4 length strings using "a" only, or using "b" only or using both.+ Using "a" one time only → 0+1+ only: {0001, 0011, 0111}
using "b" one time only → 2+3+ only : {2223, 2233, 2333}
Using two time, i.e., aa, ab, ba, bb
aa→ 0101
ab→ 0123
ba→ 2301
bb→ 2323
'Hence total 10 strings {0001, 0011, 0111, 2223, 2233, 2333, 0101, 0123, 2301, 2323}
 Question 124
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.
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2016 Aug- paper-2
Question 124 Explanation:
Option-A:​ TRUE: S is non terminal symbol, ∈ is the null string, is ambiguous.
Option-B:​ FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
Option-C:​ TRUE: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
Option-D: ​ TRUE: Recursive descent parser is a top-down parser
 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
Theory-of-Computation       Regular-Expression       UGC NET CS 2016 July- paper-2
Question 125 Explanation:
Possible strings of length 4 generated by given regular expression are:
1111, 0111, 1112, 0122, 0123, 1222, 1223, 0122, 0113, 1123, 0112, 1113.
So, total 12 strings of length 4 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
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2015 Jun- paper-2
Question 126 Explanation:
If all the production rules have single non-terminal symbol on the left side, the grammar defined is context free grammar.
Context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule
A → α replaces A with α . There can be multiple replacement rules for any given value. For example,
A → α
A → β
means that A can be replaced with either α or β.
→ In context-free grammars, all rules are one-to-one, one-to-many, or one-to-none. These rules can be applied regardless of context. The left-hand side of the production rule is always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters α and β but not A.
 Question 127
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)
Theory-of-Computation       Context-Free-Language       UGC NET CS 2004 Dec-Paper-2
Question 127 Explanation:
The context free languages are closed under union and kleene star but it is not closed under intersection and complementation.
Note: Except intersection and complementation will closed under all operations in CFL.
 Question 128
Which sentence can be generated by
S→d/bA
A→d/ccA
 A bccddd B aabccd C ababccd D abbbd E None of the above
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2005 Dec-Paper-2
Question 128 Explanation:
Here, there is no terminal symbol ‘a’, so the answer never be option B,C,D.
Option-A is also wrong because the string generated by grammar is bccccd.
 Question 129
Regular expression a+b denotes the set :
 A {a} B {ε, a, b} C {a, b} D None of these
Theory-of-Computation       Regular-Expression       UGC NET CS 2005 Dec-Paper-2
Question 129 Explanation:
The regular expression a+b denotes the set {a, 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
Theory-of-Computation       Finite-Automata       UGC NET CS 2005 june-paper-2
Question 130 Explanation:
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
 Question 131
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 }
Theory-of-Computation       Context-Free-Language       UGC NET CS 2005 june-paper-2
Question 131 Explanation:
Option-A​ is a CFL because for this we can have a non deterministic pushdown automata which will accept the string by exploring all the possibilities on each input character.
Option-B​ is correct because we can have a deterministic pushdown automata which will push all the "a" as they come as input and when "b" comes as input for every "b" one "a" will be popped. So in this way we can design a pushdown automata which will accept a​ n​ b​ n​ . Hence a​ n​ b​ n​ is a CFL.
Option-C​ is not a CFL because we can't design a pushdown which can accept CFL. Suppose a string "abcabc". Now let's say pushdown automata recognize w=abc after symbol "c" now when "a" come as input after "c" the pushdown automata have to pop "a" i.e. initial input symbol "a" but top of the stack contains "c" as top element. So in this way we can't have any pushdown automata which can accept "ww" language. So it is not a CFL.
Option-D​ is a CFL because we can design a pushdown automata for a​ n​ b​ m​ c​ m​ d​ n​ . The push down automata will push "a" and "b" as the come as input symbol. When "c" came as input then for each "c" one "b" is popped from top of the stack. And when "d" will come as input symbol the top of stack will contain only a's so for every "d" one "a" is popped . In this way we can design a pushdown automata for a​ n​ b​ m​ c​ m​ d​ n​ .
 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
Theory-of-Computation       Context-Sensitive-Grammar       UGC NET CS 2005 june-paper-2
Question 132 Explanation:
→ Phrase structure grammars(or) Phase 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.
→ Most general phase structured grammar is context sensitive grammar
 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
Theory-of-Computation       Context-Sensitive-Grammar       UGC NET CS 2005 june-paper-2
Question 133 Explanation:
Two Pass Assemblers:
Pass-1:
1. Assign addresses to all statements in the program
2. Save the values assigned to all labels for use in Pass2
3. Perform some processing of assembler directives
Pass-2:
1. Assemble instructions Generate data values defined by BYTE,WORD
2. Perform processing of assembler directives not done in Pass 1
3. Write the object program and the assembly listing
 Question 134
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)*
Theory-of-Computation       Regular-Expression       UGC NET CS 2006 Dec-paper-2
Question 134 Explanation:

It is clearly representing
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
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2006 Dec-paper-2
Question 135 Explanation:
→ 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.
→ Most general phase structured grammar is context sensitive grammar.
 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
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2006 June-Paper-2
Question 136 Explanation:
 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
Theory-of-Computation       Context-Free-Language       UGC NET CS 2014 Dec-Paper-2
Question 137 Explanation:
Option A is false: as it generate string "abab" which has even number of a's and b's.
Option B is false: as it generate string "ab" which has odd number of a's and b's.
Option D is false: as it always generate one "a" along with one "b". So it will always generate equal number of a's and b's and will never generate different number of a's and b's.
Hence option C is correct.
 Question 138
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
Theory-of-Computation       Regular-Language       UGC NET CS 2018-DEC Paper-2
Question 138 Explanation:
if L is a regular language then we always have a string “w” which can be broken into “xy” such that |y|=2|x|
Consider a language L= {a​ 3n​ | n ≥ 0} , the strings in L are {ε, aaa, aaaaaa, .......}
then L​ 1​ = {a​ n​ | n ≥ 0} as every string in L can be broken into three equal parts .
DFA for L

DFA for L​ 1

By same logic L​ 2​ is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L​ 1​ , since we can break only even length string into two equal parts such that |x| = |y| if “xy ε L”
 Question 139
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
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2018-DEC Paper-2
Question 139 Explanation:
If we have no repetition in a string then the number of substrings can be found using the formula :
n*(n+1)/2 + 1
We have added 1 because it may include a NULL string also.
The number of substrings = 10*(11)/2 +1
The number of substrings = 56
 Question 140
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
Theory-of-Computation       Context-Free-Language       UGC NET CS 2018-DEC Paper-2
Question 140 Explanation:
→ L​ 1​ is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L​ 1​ so we can say L​ 1​ is a CFL.
→ L​ 2​ is not a context free language because L is equivalent to language= {a​ p​ b​ p​ a​ p​ | p ≥ 0 }.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L​ 2​ .
L​ 2​ is not a CFL.
 Question 141
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
Theory-of-Computation       Finite-Automata       UGC NET CS 2018-DEC Paper-2
Question 141 Explanation:
● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.
● Regular languages are useful for many practical applications due to the fact that “all natural” questions concerning regular languages are decidable
 Question 142
The context free grammar for the language L = {anbmck | 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 | λ
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2014 June-paper-2
Question 142 Explanation:
L = { λ, ab, ac, bc, aabb,aabc,aac, bbc, ........}
Option(A): Option(A) will generate the string "acab" which does not belongs to the sequence anbmck . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string "acab" which does not belongs to the sequence anbmck. So, it is not the context free grammar for the language L. Option(C): In this option production S3 and S4 are unreachable so it is not the context free grammar for the language L. Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ........}. So it is the context free grammar for the language L.
 Question 143
The regular grammar for the language
L = {w|na(w) and nb(w) are both even,
w ∈ {a, b}*} is given by :
(Assume, p, q, r and s are states)
 A p → aq | br | λ, q → bs | ap r → as | bp, s → ar | bq, p and s are initial and final states. B p → aq | br, q → bs | ap r → as | bp, s → ar | bq, p and s are initial and final states. C p → aq | br | λ, q → bs | ap r → as | bp, s → ar | bq p is both initial and final states. D p → aq | br, q → bs | ap r → as | bp, s → ar | bq p is both initial and final states
Theory-of-Computation       Regular-Language       UGC NET CS 2014 June-paper-2
Question 143 Explanation:
L={ λ. ab, λab, λaabb, aabb, ..........}
Option (A): The grammar given in this option does not contain a state which is accepting a terminal "λ" , having zero number of "a" and "b". Since the grammar is not accepting λ so it not the regular grammar for the given language L.

Option (B): The grammar given in this option is not generating any string "λ" which is having zero number of "a" and "b". Since the grammar is not generating λ so it not the regular grammar for the given language L.

Option (C): Here state "p" is the initial and final state and the grammar given here is generating string "λ" , having zero number of "a" and "b". Since the grammar is accepting λ so it is the regular grammar for the given language L.

Option (D): In this option (p) is the initial and final state but the grammar is not generating any string "λ" which also belongs to the given language L. So this grammar is not the regular grammar for the given language L.

 Question 144
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
Theory-of-Computation       Regular-Expression       UGC NET CS 2018-DEC Paper-2
Question 144 Explanation:
L(s) = {∊, a, b, ab, bb, aa, ba, aab, baa,aaab, aaab,......}
L(r) = { ab, aab, aaab, aaaab, ............}
L(t) = { b, ab, aab, aaab, aaaab, .........}
L(s) can generate every possible string over a, b but L(r) and L(t) can’t generate every possible
string over a, b. So L(s)⊆L(r) and L(t)⊆L(r)
L(r) can’t generate “b” but L(t) can’t. So L(s)⊆L(t).
 Question 145
Consider the language L given by
L = { 2 nk | k > 0 , and n is non − n egative integer number }
The minimum number of states of finite automaton which accept the language L is
 A n B n+1 C 2 n D n (n + 1 )/2
Theory-of-Computation       Finite-Automata       UGC NET CS 2018-DEC Paper-2
Question 145 Explanation:
n is a positive integer constant (means it is fixed)
assume n= 2 (for instance)
then we have : L= a​ 2k​ | k>0
so k's value will be {1,2,3,4,........} and accordingly in L we have strings {a​ 2​ ,a​ 4​ ,a​ 6​ , a​ 8​ .......}
→ ​ It is clearly even number of a's (except zero a's)​ ​ and for this we have 3 state DFA,
→ ​ If n=3 then we will have a​ 3​ , a​ 6​ , a​ 9​ ..........
→ So, we require 4 state DFA
hence answer will be "n+1" states are required.
 Question 146
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 = Σ* ?
Theory-of-Computation       Decidability-and-Undecidability       UGC NET CS 2018-DEC Paper-2
Question 146 Explanation:
→ A language is called Decidable or Recursive if there is a Turing machine which accepts and halts on every input string w.
→ Every decidable language is Turing-Acceptable.
→ For recursive language membership problem is decidable, i.e., a string “w” belongs to a recursive language “L” is decidable. Rest all are undecidable.
→ If language is recursive then it means , we have a Turing machine for the language which always halt. So when a string “w” is given to this turing machine it always halt either by accepting “w” or by rejecting “w”. Hence “Is w∈L” is decidable.
 Question 147
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 (L 1 ⋃ L 2 ) − R is context free B L 1 − R is context free C L 1 is context free D L 1 ⋂ L 2 is context free
Theory-of-Computation       Regular-Language       UGC NET CS 2018-DEC Paper-2
Question 147 Explanation:
Option 1: L​ 1 ​ and L​ 2​ are context free languages and context free languages are closed under union but not closed under complementation. It means intersection result may or may not br CFL. So when we will do subtraction the result may or may not be CFL.
Option 2: L​ 1​ is a CFL and R is a Regular language and if we do L​ 1​ - R the result will Regular language.
L​ 1 ​ = {a​ n​ b​ n​ | n>0} is a context free language which can generate strings {ab, aabb, aaabbb, .......}
R = (a+b)* which can generate language {∈, a, b, aa, bb, ab, ba, .......}
So L​ 1​ -R = {ф} which is a regular language.
And since every regular language is also a CFL so option 2 is correct.
Option 3: context free languages are not closed under complementation. So option 3 is incorrect.
Option 4: context free languages are not closed under Intersection. So option 4 is incorrect.
 Question 148
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
Theory-of-Computation       DFA       UGC NET CS 2013 Sep-paper-2
Question 148 Explanation:
L={aaaa, aaaaa, aaaaaa, .........}
The minimal DFA accepting the given language L is given below:

Hence the number of states in a minimal deterministic finite automaton corresponding to the language L is 5.
 Question 149
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 + λ)
Theory-of-Computation       Regular-Expression       UGC NET CS 2013 Sep-paper-2
Question 149 Explanation:
L={ null, 0, 1, 01, 10, 11, 010, 011, 101, 110, 111, ...........}
Option A is incorrect because it can generate 010010 string which is having a pair of consecutive zeros.
Option B is incorrect because it can generate 1001 string which is having a pair of consecutive zeros.
Option C is incorrect because it can generate 0100 string which is having a pair of consecutive zeros.
Option D is correct because it will generate all the strings mentioned in the given language L
 Question 150
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
Theory-of-Computation       Regular-Language       UGC NET CS 2013 Sep-paper-2
Question 150 Explanation:
→ L1 is regular → L2 is not a regular language because of "k≤ l" condition, this condition needs the machine which can remember number of b's in the language so that number of a's following "b" can be compared. Since Finite automata don't have any memory unit to remember the previous inputs, So it can't accept the language L2. Hence L2 is not a regular language.
 Question 151
LL grammar for the language L = {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| λ|
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2013 Sep-paper-2
Question 151 Explanation:
L1 is the language when n=0, m=0.
L1={λ}
L2 is the language when only n=0
L2={bc, bbcc, bbbccc,......}
L3 is the language when only m=0
L3={ ac, aacc, aaaccc, ........}
L4 is the language when n≠0 and m≠0
L4= {abcc, aabbcccc, aaabbbcccccc,...............}
L= {L1 U L2 U L3 U L4}
L= { λ, bc, bbcc, bbbccc,........, ac, aacc, aaaccc,.........., abcc, aabbcccc,aaabbbcccccc,.........}
Option A is incorrect because it does not have any stoping point for condition when m=0 i.e it can't generate strings { ac, aacc, aaaccc, ........}
Option B is incorrect because it does not have any stopping point for condition when n=0 i.e it can't generate strings {bc, bbcc, bbbccc,......}
Option C is correct because it can generate all the strings generated by the language L.
Option D is incorrect because state S1 is unreachable in it. And because of this strings {bc, bbcc, bbbccc,......{abcc, aabbcccc, aaabbbcccccc,...............} can't be generated.
 Question 152
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.
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2013 Sep-paper-2
Question 152 Explanation:
Statement S1 is correct because finiteness problem of CFG is decidable
. Statement S2 is incorrect because equality problem (L1 = L2; where L1 and L2 are CFL) of CFG is undecidable .
 Question 153
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
Theory-of-Computation       Finite-Automata       UGC NET CS 2018 JUNE Paper-2
Question 153 Explanation:
We can call two finite state machines as equivalent if and only if the accept the same language.
 Question 154
The finite state machine given in figure below recognizes :
 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
Theory-of-Computation       Finite-Automata       UGC NET CS 2018 JUNE Paper-2
Question 154 Explanation:
The language accepted by above finite automata is:
L = {ab,ba,ababab, bababa,..........}
Here L is the language containing odd number of a’s and odd number of b’s.
 Question 155
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
Theory-of-Computation       Turing-machines       UGC NET CS 2018 JUNE Paper-2
Question 155 Explanation:
→ If we have two stacks then the stacks can act as a queue. Since a pushdown automata have a single stack as its memory device so if we have 1 more stack then the pushdown automata can be made to act as a turing machine.
→ So, total of 2 or more auxiliary memory are needed to make a pushdown automata behaves like a Turing machine.
 Question 156
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
Theory-of-Computation       Push-Down-Automata       UGC NET CS 2018 JUNE Paper-2
Question 156 Explanation:
Let A➝ aA | ∈ ; Here A is a regular grammar which can be accepted by the pushdown automata
B➝ aBb | ab ; Here B is a Context free grammar which can be accepted by the pushdown automata
 Question 157
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
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2018 JUNE Paper-2
Question 157 Explanation:
If all the productions of a grammar are in the form A➝BC OR A➝a then that grammar is said to be in Chomsky normal form.
Example:
S → A B
A → a
B → b
Derive string “ab” from above grammar.
Detailed explanation for example:

Using formula 2 n − 1 ; where n = length of string
2 (2) − 1 = 3
 Question 158
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
Theory-of-Computation       Context-sensitive-language       UGC NET CS 2018 JUNE Paper-2
Question 158 Explanation:
Context sensitive languages can be recognized by the Linear bounded automata.
L= { a n b n c n | where n > 0 }
is a context sensitive language and cannot be recognized by Finite state machine, Deterministic finite automata, Non-deterministic finite automata but L can be recognized by Linear Bounded Automata.
So Context Sensitive Language can be recognized by Linear Bounded Automata.
 Question 159
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
Theory-of-Computation       Context-Sensitive-Grammar       UGC NET CS 2018 JUNE Paper-2
Question 159 Explanation:
→ For above set we need infinite tape so this can’t be an example of Regular Grammar.
→ In case of Context Free grammar we have a stack only in which we can push 0’s as they come as input and can POP 0’s as 1’s come as input but when 2’s comes as input string we have NULL at the top of the stack so this Grammar can’t be a context free grammar.
→ Since in case of Context sensitive grammar we have linear bounded automata and a read/write head which can move backward and upward so this grammar can be accepted by Linear Bounded Automata. So this grammar is a Context Sensitive Grammar.
 Question 160
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
Theory-of-Computation       Turing-machines       UGC NET CS 2018 JUNE Paper-2
Question 160 Explanation:
→ Checking if any two Turing machines M1 and M2 accept the same language or not is the equivalence problem. And equivalence problem of turing machines is Undecidable. So Statement S1 is correct.
→ Halting problem of a turing machine is undecidable because if a turing machine accepts a string then it will halt but if a turing machine does not accept a string then it may or may not halt(can enter infinite loop). So statement S2 is also correct.
 Question 161
The ‘C’ language is
 A Context free language B Context sensitive language C Regular language D None of the above
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2012 Dec-Paper-2
Question 161 Explanation:
C and C++ are context sensitive languages.
 Question 162
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|
Theory-of-Computation       Finite-Automata       UGC NET CS 2012 Dec-Paper-2
Question 162 Explanation:
The maximum number of states possible in a finite automaton which is equivalent to given non-deterministic finite automaton having with |Q| states is 2^|Q|
 Question 163
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 | λ
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2013 Dec-paper-2
Question 163 Explanation:
According to given the given language L when
m=0, n<= 3 i.e. L1= { λ, a, aa, aaa}
m=1, n<=4 i.e. L2={ ab, aab, aaab, aaaab}
m=2, n<=5 i.e. L3={abb, aabb, aaabb, aaaabb, aaaaabb} and so on.
Hence L = L1 U L2 U L3 U ...........
L= { λ, a, aa, aaa, ab, aab, aaab, aaaab, abb, aabb, aaabb, aaaabb, aaaabb, .................}
Option(A) is not correct because it can't generate λ.
Option(B) is not correct because it can't generate "a".
Option(C) is not correct because it can't generate "a".
Option(D) is correct because it is generating the language L
.
 Question 164
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.
Theory-of-Computation       Regular-Language       UGC NET CS 2013 Dec-paper-2
Question 164 Explanation:
→ Statement S1 is correct. "uv" in given language can also be written as "LLR " . Since L is a regular language and we know that a regular language is closed under reverse operation then LR is also a regular language. Regular language is closed under concatenation then LLR is also a regular language.
→ Statement S2 is incorrect. Since the finite state automata do not have a memory element which can remember the previous inputs hence the string "w" can't be recorded in order to match/compare with "wR ". So we can't have a Finite state automata for wwR. And since we can't have Finite state automata for wwR , it means wwR is not a regular language.
Hence the correct option is option(C)
 Question 165
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
Theory-of-Computation       Closure-Property       UGC NET CS 2012 June-Paper2
Question 165 Explanation:
→ Recursive closed under union,intersection,complementation,etc.., except Homomorphism and substitution.
→ Recursively enumerable languages are closed under union,intersection,etc.., except set difference and complementation.
 Question 166
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
Theory-of-Computation       Context-Free-Language       UGC NET CS 2011 Dec-Paper-2
Question 166 Explanation:
Context-free languages are closed under Union,Concatenation and Kleene closure.
Context-free languages are not closed under set difference,Complementation and intersection.
 Question 167
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
Theory-of-Computation       Pumping-Lemma       NIELIT Junior Teachnical Assistant_2016_march
 Question 168
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
Theory-of-Computation       Context-Free-Language       NIELIT Junior Teachnical Assistant_2016_march
 Question 169
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
Theory-of-Computation       Regular-Expression       UGC NET CS 2013 June-paper-2
Question 169 Explanation:
L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2
L1={ba, baa, baaa, .........................aba, aaba, aaaba,................abaa, abaaa, ....................}
L2={a, ab, abb, abbb, ..........................}
Take "a" from L1:
L1/a ={ b, ba, baa, .................ab, aab, aaab, ....................aba, abaa, .....................}
So we get : a*ba*
If you take "ab" from L2
Like:
L1/ab = you will not get any string i,e. empty set will be in result in case of L1/ab
as no string in L1 end with "ab"
 Question 170
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
Theory-of-Computation       Finite-Automata       UGC NET CS 2013 June-paper-2
Question 170 Explanation:

 Question 171
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.
Theory-of-Computation       Finite-Automata       NIELIT Technical Assistant_2016_march
 Question 172
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
Theory-of-Computation       Moore-and-Mealy-Machine       NIELIT Technical Assistant_2016_march
 Question 173
“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.
Theory-of-Computation       Regular-Expression       UGC NET CS 2010 June-Paper-2
Question 173 Explanation:
m is generating single "a".
If you observe all of them is generating (aba)x
Note: This question is ambiguous, the wordings are not very clear.
 Question 174
Which of the following is the most general phase structured grammar ?
 A Regular B Context-sensitive C Context free D None of the above
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2010 June-Paper-2
Question 174 Explanation:
→ 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.
→ Most general phase structured grammar is context sensitive grammar.
 Question 175
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
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2009-June-Paper-2
Question 175 Explanation:
Context-free Grammar (CFG) can be recognized by finite state automata and linear bounded automata(LBA).

 Question 176
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)
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2009 Dec-Paper-2
Question 176 Explanation:
Context-free Grammar (CFG) can be recognized by finite state automata and linear bounded automata(LBA).

 Question 177
A context free grammar is :
 A type 0 B type 1 C type 2 D type 3
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2007-Dec-Paper-2
Question 177 Explanation:

 Question 178
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.
Theory-of-Computation       Moore-and-Mealy-Machine       UGC NET CS 2007-Dec-Paper-2
Question 178 Explanation:
In the given state diagram it can be clearly noticed that the minimum string that is accepted by the moore machine M is "bb". So the language can contain 0 or more number of a's and 2 or more number of b's.
 Question 179
The following deterministic finite automata recognizes :

 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
Theory-of-Computation       Finite-Automata       UGC NET CS 2007 June-Paper-2
Question 179 Explanation:
There is no final state in the given deterministic finite automata so it can't accept any string. Hence the answer is option(D)
 Question 180
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’
Theory-of-Computation       Regular-Expression       UGC NET CS 2007 June-Paper-2
Question 180 Explanation:
L= { λ, 0, 1λ, 01λ, 10, 010, 110, .............}
According to the language L generated by given regular expression
Option(A) is incorrect because L contains 110.
Option(B) is correct because no string is containing 00
Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.
Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.
Hence correct answer is option (B)
 Question 181
Which of the following language is regular :
 A L = { an bn| n ≥ 1 } B L = { an bm cn dm|n, m ≥ 1 } C L = { an bm|n, m ≥ 1 } D L = { an bm cn|n, m ≥ 1 }
Theory-of-Computation       Regular-Language       UGC NET CS 2007 June-Paper-2
Question 181 Explanation:
Language generated in Option (A) requires a memory element to count equal number of b's after a. And since regular languages are accepted by finite automata which does not have a memory element. Hence Option (A) language is not Regular.
Language generated in Option (B) requires a memory element and a read write head which can move in both the directions to count equal number of a's and c's , and b's and d's. And since regular languages are accepted by finite automata which does not have a memory element and a read write head which can move in both the directions. Hence Option (A) language is not Regular.
Language generated in Option (C) is regular because number of a's and b's is not necessarily need to be same which means no memory element is required. Hence it is a regular language.
Language generated in Option (D) requires a memory element to count equal number of c's after a. And since regular languages are accepted by finite automata which does not have a memory element. Hence Option (A) language is not Regular. The language generated here is context free language which can be accepted by pushdown automata.
 Question 182
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
Theory-of-Computation       Regular-Language       UGC NET CS 2017 Nov- paper-3
Question 182 Explanation:
Pumping lemma for regular language is generally used for proving a given grammar is not regular.
 Question 183
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
Theory-of-Computation       Decidability-and-Undecidability       UGC NET CS 2017 Nov- paper-3
 Question 184
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
Theory-of-Computation       Finite-Automata       UGC NET CS 2017 Nov- paper-3
 Question 185
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.
Theory-of-Computation       Languages-and-Grammars       UGC NET CS 2017 Nov- paper-3
Question 185 Explanation:
→ The given language is Context free language(CFL) because we can push a's onto the top of stack as a's come as input and when a "b" come as input don't push it on the top of stack just change the state and after that when c's come come as input pop one "a" from top of stack for each "c".
→ In this way the given language can be accepted by the deterministic pushdown automata and hence the language is deterministic context free language. And when a language is CFL it is also a recursive language.
Hence the correct answer is option (C)
 Question 186
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.
Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       UGC NET CS 2017 Nov- paper-3
Question 186 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.
→ Recursive closed under union,intersection,complementation,etc.., except Homomorphism and substitution.
FALSE: Recursive languages are not closed under intersection.
→ Recursively enumerable languages are closed under union,intersection,etc.., except set difference and complementation.
 Question 187
Context free grammar is not closed under:
 A Concatenation B Complementation C Kleene Star D Union
Theory-of-Computation       Context-Free-Grammar       UGC NET CS 2017 Nov- paper-3
Question 187 Explanation:
→ Context-free grammar are closed under Union,Concatenation and Kleene closure.
→ Context-free grammar are not closed under set difference,Complementation and intersection.
 Question 188
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
Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Nov- paper-3
Question 188 Explanation:
L1={am bn | m≠n }
→ It means m could be greater than or less than ‘n’ but m will not be equal to ‘n’.
→ Since for accepting the language L1 we need a storage so then no. of a’s can be stored in it and when b’s come as input a’s and b’s can be compared.
→ Since finite automata do not have a storage element hence the language is not regular.
→ Now state transition diagram to check whether L1 is CFL or not:

→ Hence L2 is also a CFL.
L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
There are 188 questions to complete.