subject – solutions adda

Theory-of-Computation

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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 = {aⁿ bⁿ \| 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 = {aⁿ bⁿ | 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	2^x

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

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 6 Explanation:

According to the Chomsky hierarchy, both the statements are correct.

Question 7

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 7 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 8

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 8 Explanation:

Option C is correct because it indicates L followed by (L + D)* where * means 0 or more occurences of L or D.

Question 9

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 9 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 10

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 10 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 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	{a^mbⁿ \| n>=m, m>0}
B	{a^mbⁿ \| n>=m, m>=0}
C	{a^mbⁿ \| n>m, m>0}
D	{a^mbⁿ \| 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 a^mbⁿ | n>m, m>=0

Question 14

Let L₁ be regular language, L₂ be a deterministic context free language and L₃ a recursively enumerable language, but not recursive. Which one of the following statements is false?

A	L₁ ∩ L₂ is context-free
B	L₃ ∩ L₁ is recursive
C	L₁ ∪ L₂ is context-free
D	L₁ ∩ L₂ ∩ L₃ 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 L₁ ∩ L₂ is a deterministic CFL.
→ Option B is false, as L₃ is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.
→ Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L₁ ∪ L₂ is deterministic context free, hence it is also context free.
→ Option D is true, as L₁ ∩ L₂ is DCFL and DCFL ∩ L₃ 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 = {a^p| 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 = {a^p | 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	(0101)*
B	0(1010)
C	0(101)0*
D	01(101)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	q₀, q₁, q₂
B	[q₀, q₁], [q₀, q₂], [ ]
C	q₀, [q₁, q₂]
D	[q₀, q₁], q₂

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 2ⁿ
B	2^m+n
C	2^mn
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 2^x states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2^mn.

Question 26

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	10 {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 = {aⁿbⁿcⁿ| 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 = { 0ⁿ 1ⁿ 2ⁿ | 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	abb
B	ab
C	b*b
D	bab

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 {W^a X^b Y^a+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

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 47 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 48

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 48 Explanation:

Two automata M₀ and M ₁ are said to be equivalent to each other if both accept exactly the same set of input strings.

Question 49

Consider the following two languages:

₁

= {x | for some y with

|y|=

^|x|

, xy ∈ L and L is regular language}

₂

= { 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 L₁ and L₂ are regular languages
B	Both L₁ and L₂ are not regular languages
C	Only L₁ is regular language
D	Only L₂ is regular language

Theory-of-Computation Finite-Automata UGC-NET DEC Paper-2

Question 49 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³ⁿ | n ≥ 0} , the strings in L are {ϵ, aaa, aaaaaa, …….}
then L₁ = {aⁿ | n ≥ 0} as every string in L can be broken into three equal parts.
DFA for L:

DFA for L₁:

By same logic L₂ 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₁, since we can break only even length string into two equal parts such that |x| = |y| if “xy ∈ L”.

Question 50

Consider the following language:

L₁

= {

a^n+m

bⁿ

a^m

| n,m ≥ 0

}

L₂

= {

a^n+m

b^n+m

a^n+m

|n,m ≥ 0

}

Which one of the following is correct?

Code:

A	Only L₁ is Context Free Language
B	Both L₁ and L₂ are not Context Free Language
C	Only L₁ is Context Free Language
D	Both L₁ and L₂ are Context Free Language

Theory-of-Computation Context-Free-Language UGC-NET DEC Paper-2

Question 50 Explanation:

→ L₁ 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₁ so we can say L₁ is a CFL.
→ L₂ is not a context free language because L is equivalent to language = {a^pb^pa^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₂.
L₂ is not a CFL.

Question 51

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 51 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 52

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 52 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 53

Consider the language L given by

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

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

A	n
B	n+1
C	2ⁿ
D	n(n+1)/2

Theory-of-Computation Finite-Automata UGC-NET DEC Paper-2

Question 53 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², a⁴, a⁶, a⁸ .......}
→ 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³, a⁶, a⁹ ..........
→ So, we require 4 states DFA
Hence answer will be "n+1" states are required.

Question 54

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 54 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 55

Consider R to be any regular language and L₁.L₂ 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 55 Explanation:

Option 1: L₁ and L₂ 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₁ is a CFL and R is a Regular language and if we do L₁ - R the result will Regular language.
L₁ = {aⁿ bⁿ | 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₁ - 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 56

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 56 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 57

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 57 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 58

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 enumerable
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 58 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 59

Which of the following problems are decidable?

Does a given ever produce an output?
If L is a context free language, then is L’ (complement of L) also context free?
If L is a regular language, then is L’ also regular?
If L is a recursive language, then is L’ also recursive?

A	(a), (b), (c), (d)
B	(a), (b)
C	(b), (c), (d)
D	(c), (d)

Theory-of-Computation Nielit STA [02-12-2018]

Question 59 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 60

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 60 Explanation:

Context free languages closed under Union, concatenation and kleene star. But not close under intersection and complementation.

Question 61

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 61 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 62

Given language L={a^(2*m)c^(4*n)dⁿb^m | 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 62 Explanation:

It generate the string is L={ aaccccdb, aaaaccccccccddbb….,}. So, it is push down automata. It require one stack memory.

Question 63

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 64

Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a,b}?

A	ab
B	(a \| b)*
C	(ab) *
D	(a \| b*)

Theory-of-Computation Regular-Expression Nielit Scientist-B CS 2016 march

Question 64 Explanation:

It is clearly saying that all possible strings over the alphabet {a,b} is (a | b)*

Question 65

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 65 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 66

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 66 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 67

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 67 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 68

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 69

Which of the following statements is correct?

A	A={aⁿbⁿ \|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(AB) ∩ B gives the set A
D	None of these

Theory-of-Computation Regular-Language Nielit Scientist-B CS 2016 march

Question 69 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 70

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 70 Explanation:

Regular sets are closed under union, concatenation and Kleene closure

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

Consider the following two languages:
L ₁ = {x | for some y with | y| = 2 ^|x| ,xy∈ L and L is regular language}
L ₂ = { 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 ₁ and L₂ are regular languages
B	Both L ₁ and L ₂ are not regular languages
C	Only L ₁ is regular language
D	Only L ₂ is regular language

Theory-of-Computation Regular-Language UGC NET CS 2018-DEC Paper-2

Question 72 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 ₁ = {aⁿ | n ≥ 0} as every string in L can be broken into three equal parts .
DFA for L

DFA for L ₁

By same logic L ₂ 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₁ , since we can break only even length string into two equal parts such that |x| = |y| if “xy ε L”

Question 73

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 73 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 74

Consider the following language:
L ₁ = { a^n+m bⁿ a^m | n, m ≥ 0 }
L ₂ = { a^n+m b^n+m a^n+m |n, m ≥ 0 }
Which one of the following is correct?

A	Only L₁ is Context Free Language
B	Both L ₁ and L₂ are not Context Free Language
C	Only L ₁ is Context Free Language
D	Both L₁ and L₂ are Context Free Language

Theory-of-Computation Context-Free-Language UGC NET CS 2018-DEC Paper-2

Question 74 Explanation:

→ L ₁ 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 ₁ so we can say L ₁ is a CFL.
→ L ₂ 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₂ .
L ₂ is not a CFL.

Question 75

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 75 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 76

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 76 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 77

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 ⁿ
D	n (n + 1 )/2

Theory-of-Computation Finite-Automata UGC NET CS 2018-DEC Paper-2

Question 77 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 ² ,a⁴ ,a⁶ , a⁸ .......}
→ 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 ³ , a⁶ , a⁹ ..........
→ So, we require 4 state DFA
hence answer will be "n+1" states are required.

Question 78

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 78 Explanation:

Question 79

Consider R to be any regular language and L₁ .L₂ be any two context-free languages Which one of the following is correct ?

A	(L ₁ ⋃ L₂ ) − R is context free
B	L ₁ − R is context free
C	L ₁ is context free
D	L ₁ ⋂ L₂ is context free

Theory-of-Computation Regular-Language UGC NET CS 2018-DEC Paper-2

Question 79 Explanation:

Option 1: L ₁ and L₂ 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 ₁ is a CFL and R is a Regular language and if we do L ₁ - R the result will Regular language.
L ₁ = {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 ₁ -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 80

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 80 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 81

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 82

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 82 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 83

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 83 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 84

(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 84 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 85

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 85 Explanation:

Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleene-closure
Σ* - R₁ is the complement of R₁.

Question 86

State whether TRUE or FALSE

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 86 Explanation:

Formal Definition of an NDFA
An NDFA can be represented by a 5-tuple (Q, ∑, δ, q₀, F) where
Q is a finite set of states.
∑ is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2^Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
q₀ is the initial state from where any input is processed (q₀ ∈ 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 87

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 87 Explanation:

Kleene closure
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).

Question 88

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 88 Explanation:

→ All possible strings of length 2 over Σ = {a,b} = 4(aa,ab,ba,bb}.
→ We are computing all possible strings using 2ⁿ formula. Where n is number of strings.

Question 89

A DFA can be expressed as a 5 tuple(Q, Σ, δ, q₀, 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 89 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 90

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 90 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 91

Which of the definitions generates the same languages as L, where
L={ xⁿ yⁿ , 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 91 Explanation:

The language L={ x ⁿ yⁿ , n>=1 }
For n=1, xy
n=2,x ² y²
n=3,x ³ y³
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 92

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)⁴
B	(0+1)⁴
C	(01)⁴
D	(0+1+ɛ)⁴

Theory-of-Computation Nielit Scientist-B 17-12-2017

Question 92 Explanation:

The extended notation would be (0+1)⁴ but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.

Question 93

Let G be a grammar in CFG and Let W ₁,W₂ɛ L(G) such that |W₁|=|W₂| then which of the following statement is TRUE?

A	Any derivation of W₁ has exactly the same number of steps as any derivation of W₂
B	Different derivation have different length
C	Some derivation of W₁ may be shorter the derivation of W₂
D	None of the options

Theory-of-Computation Nielit Scientist-B 17-12-2017

Question 93 Explanation:

Given data,
W₁ and W₂ are 2 strings,
|W₁|=|W₂| means same length
Example CFG grammar:
S→ Cbb | cc
C→ a
W₁=cc W₂=Cbb
As per the grammar, W₁ require only one derivation S→ cc
W₂ requires two derivations S→ Cbb→ abb
It means W₁ is smaller than W₂.

Question 94

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 94 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 95

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 95 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 96

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 96 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 97

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 97 Explanation:

∑* means it may be zero or any string. The above regular expression should contain 001.

Question 98

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 98 Explanation:

Question 99

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 99 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 100

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 100 Explanation:

The collection of turing recognizable languages are closed under
1)Union
2)Intersection
3)Concatenation
4)Star closure

Question 101

Which of the following regular expression is equal to (r1+r2)*?

A	r1r2
B	(r1r2)*
C	r1r2+r1r2
D	(r1r2)*

Theory-of-Computation Nielit Scientist-B 17-12-2017

Question 101 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 102

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 102 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 103

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 103 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 104

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 104 Explanation:

Every 11 followed by 0 and no single occurrence of 1 is possible. So it cannot generate 1101 (or) 11011

Question 105

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	n² +1
C	n² -1
D	n(n+1)/2

Theory-of-Computation Nielit Scientist-B 17-12-2017

Question 105 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(n³) time in worst case.

Question 106

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 106 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 107

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 107 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 108

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 108 Explanation:

Question 109

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 109 Explanation:

→ Deterministic turing machine and nondeterministic turing machine are same in terms of power.
→ NPDA is more powerful than DPDA.

Question 110

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 110 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 111

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 111 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 112

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 112 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 113

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 113 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 114

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 114 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 115

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 115 Explanation:

If L1 and If L2 are two regular languages, their intersection L1 ∩ L2 will also be regular.
Example
L1= {a^m bⁿ| n ≥ 0 and m ≥ 0} and L2= {a^m bⁿ ∪ bⁿ a^m | n ≥ 0 and m ≥ 0}
L3 = L1 ∩ L2 = {a^m bⁿ | n ≥ 0 and m ≥ 0} is also regular.

Question 116

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	QP
D	(PQ)*

Theory-of-Computation Nielit STA 17-12-2017

Question 116 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+QP²+QP³…..
R=Q(ε+P+P²+P³+…. )
R=QP*[As P* represents (ε+P+P2+P3+….)]

Question 117

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 117 Explanation:

Question 118

(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 118 Explanation:

(0+ɛ)(1+ɛ) represents {0,1,ɛ}

Question 119

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 119 Explanation:

Both NFA and DFA having same computational power, as both defines the same class of regular languages.

Question 120

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 120 Explanation:

Number of DFA’s = 2ⁿ * n^(2*n)
=2²*2⁴
=4*16
=64

Question 121

Complement of (a+b)* will be:

A	π
B	∅
C	a
D	b

Theory-of-Computation Nielit STA 17-12-2017

Question 121 Explanation:

Given expression accept all string so complement will accept nothing

Question 122

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 122 Explanation:

Finite automata doesn’t require any stack operation

Question 123

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 123 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 124

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 124 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 125

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 125 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 126

Which of the definitions generates the same languages as L, where
L={ xⁿ yⁿ , 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 126 Explanation:

The language L={ x ⁿ yⁿ , n>=1 }
For n=1, xy
n=2,x ² y²
n=3,x ³ y³
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 127

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 127 Explanation:

We can’t generate the strings “a” and “b” because the Starting symbol is R→ XRX|S.

Question 128

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	01 ⁺ 01*
B	010 ⁺ 1*
C	010*1 ⁺
D	0⁺101*

Theory-of-Computation Regular-Expression UGC NET CS 2017 Nov- paper-2

Question 128 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 129

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 129 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 130

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 130 Explanation:

This problem looks very difficult but solving procedure is very easy.
Given regular expression is p+[3-5]*[xyz]
It means we have to start with p.
[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 131

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 131 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 132

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 132 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 133

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 133 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 134

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 134 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 135

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 135 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 136

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 136 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 137

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 137 Explanation:

The regular expression a+b denotes the set {a, b}.

Question 138

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 138 Explanation:

Question 139

Identify the language which is not context-free.

A	L = { wwR ǀ wε{0,1}* }
B	L = { a ⁿ bⁿ ǀ n≥0 }
C	L = { ww ǀ wε{0,1}* }
D	L = { a ⁿ b^m c^m dⁿ ǀ n,m ≥0 }

Theory-of-Computation Context-Free-Language UGC NET CS 2005 june-paper-2

Question 139 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 ⁿ bⁿ 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 ⁿ b^m c^m d ⁿ .
So, option-C is correct answer.

Question 140

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 140 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 141

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 141 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 142

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 142 Explanation:

It is clearly representing
aa*b

Question 143

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 143 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 144

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 144 Explanation:

Question 145

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 145 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 146

The context free grammar for the language L = {aⁿb^mc^k | k = |n – m|, n ≥ 0, m ≥ 0, k ≥ 0} is

A	S → S₁S₃, S₁ → aS₁c \| S₂\| λ, S₂ → aS₂b\|λ, S₃→ aS₃b\| S₄ \| λ, S₄ → bS₄c\|λ
B	S → S₁S₃, S₁→ aS₁S₂c \| λ, S₂ → aS₂b\|λ, S₃ → aS₃b\| S₄ \|λ, S₄ → bS₄c\|λ
C	S → S₁\|S₂, S₁→ aS₁S₂c \| λ, S₂ → aS₂b \| λ, S₃ → aS₃b \| S₄ \|λ, S₄ → bS₄c\|λ
D	S → S₁ \| S₃, S₁→ aS₁c\|S₂ \| λ, S₂ → aS₂b \| λ, S₃ → a S₃b\| S₄ \| λ, S₄ → bS₄c \| λ

Theory-of-Computation Context-Free-Grammar UGC NET CS 2014 June-paper-2

Question 146 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 aⁿb^mc^k . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string "acab" which does not belongs to the sequence aⁿb^mc^k. So, it is not the context free grammar for the language L. Option(C): In this option production S₃ and S₄ 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 147

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 147 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 148

The number of states in a minimal deterministic finite automaton corresponding to the language L = { aⁿ | 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 = {aⁿ b^l a^k | n + l + k>5 }
L2 = {aⁿb^l a^k | n>5, l >3, k≤ l }
Which of the following is true ?

A	L₁ is regular language and L₂ is not regular language.
B	Both L₁ and L₂ are regular languages.
C	Both L₁ and L₂ are not regular languages.
D	L₁ is not regular language and L₂ 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 = {aⁿ b^m c^n+m | m≥0, n≥0} is

A	S → aSc \| S₁ ; S₁ → bS₁c \| λ
B	S → aSc \| S₁\| λ ; S₁ → bS₁c
C	S → aSc \| S₁\| λ ; S₁ → bS₁c\| λ
D	S → aSc \| λ ; S₁ → bS₁c\| λ\|

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 S₁ and S₂ given as : S₁ : Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite. S₂ : There exists an algorithm to determine whether two context free grammars generate the same language. Which of the following is true ?

A	S₁ is correct and S₂ is not correct.
B	Both S₁ and S₂ are correct.
C	Both S₁ and S₂ are not correct.
D	S₁ is not correct and S₂ 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

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 153 Explanation:

C and C++ are context sensitive languages.

Question 154

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 154 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 155

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 155 Explanation:

We can call two finite state machines as equivalent if and only if the accept the same language.

Question 156

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 156 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 157

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 157 Explanation:

Question 158

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 158 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 159

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 ²

Theory-of-Computation Context-Free-Grammar UGC NET CS 2018 JUNE Paper-2

Question 159 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
Hence the answer is option(1)

Question 160

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 160 Explanation:

Context sensitive languages can be recognized by the Linear bounded automata.
L= { a ⁿ bⁿ cⁿ | 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 161

The set A={ 0 ⁿ 1ⁿ 2ⁿ | 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 161 Explanation:

Question 162

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 162 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 163

The context free grammar for the language L = {aⁿ b^m | 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 :
S₁ : If L is a regular language then the language {uv | u ∈ L, v ∈ L^R} is also regular.
S₂ : L = {ww^R} is regular language. Which of the following is true ?

A	S₁ is not correct and S₂ is not correct.
B	S₁ is not correct and S₂ is correct.
C	S₁ is correct and S₂ is not correct.
D	S₁ is correct and S₂ 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 "LL^R " . Since L is a regular language and we know that a regular language is closed under reverse operation then L^R is also a regular language. Regular language is closed under concatenation then LL^R 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 "w^R ". So we can't have a Finite state automata for ww^R. And since we can't have Finite state automata for ww^R , it means ww^R is not a regular language.
Hence the correct option is option(C)

Question 165

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

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 170

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 171

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	abaa
C	aba
D	None of the above

Theory-of-Computation Regular-Expression UGC NET CS 2013 June-paper-2

Question 171 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 172

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 172 Explanation:

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)3^x–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:

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 = { aⁿ bⁿ\| n ≥ 1 }
B	L = { aⁿ b^m cⁿd^m\|n, m ≥ 1 }
C	L = { aⁿ b^m\|n, m ≥ 1 }
D	L = { aⁿ b^m cⁿ\|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 = {aⁱ b cⁱ │ 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 = {0ⁿ1ⁿ 0ⁿ │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 = {0ⁿ1ⁿ 0ⁿ │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: L₁ = {a^m bⁿ │ m ≠ n} L₂ = {a^m bⁿ │ m = 2n+1} L₃ = {a^m b^m │ m ≠ 2n} Which one of the following statement is correct ?

A	Only L₁ and L₂ are context free languages
B	Only L₁ and L₃ are context free languages
C	Only L₂ and L₃ are context free languages
D	L₁, L₂ and L₃ are context free languages

Theory-of-Computation Context-Free-Language UGC NET CS 2017 Nov- paper-3

Question 188 Explanation:

L₁={a^m bⁿ | 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 L₂ is also a CFL.
L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.

Question 189

Which of the following are not regular?

(A) Strings of even number of a’s.

(B) Strings of a’s, whose length is a prime number.

(C) Set of all palindromes made up of a’s and b’s.

(D) Strings of a’s whose length is a perfect square.

A	(A) and (B) only
B	(A), (B) and (C) only
C	(B), (C) and (D) only
D	(B) and (D) only

Theory-of-Computation Regular-Language UGC NET CS 2017 Jan- paper-3

Question 189 Explanation:

Option (A):

For even no. of a’s finite automata can be constructed so it is regular.
Option (B):
L = { a², a³, a⁵, a⁷, a¹¹, a¹³, a¹⁷...................}
It is not regular language. A language is regular if the difference between two consecutive strings is same or we can say the language is in AP(arithmetic progression). But here if you see the difference between two consecutive strings/terms is not same. Hence it is not regular.
Statement (C):
L = {ab, aabb, ................... abab, baba, ababa, aababa, baabb, ..................}
It is also not regular language because the difference between two consecutive strings/terms is not same.
Statement (D): L = { a¹, a⁴, a⁹, a¹⁶, a²⁵, a³⁶, a⁴⁹...............}
It is also not regular language because the difference between two consecutive strings/terms is not same.

Question 190

Consider the languages L1 = φ and L2 = {1}. Which one of the following represents L*₁∪ L*₁ L*₂ ?

A	{∈}
B	{∈, 1}
C	ϕ
D	1*

Theory-of-Computation Languages-and-Grammars UGC NET CS 2017 Jan- paper-3

Question 190 Explanation:

As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L₁ L₂ * = ϕ
and L₁ * = {ϕ}* = {ϵ}
So L₁L₂* ∪ L₁* = {ϵ}

Question 191

Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?

A	Both (A) and (B) are false.
B	Both (A) and (B) are true.
C	(A) is true, (B) is false.
D	(A) is false, (B) is true.

Theory-of-Computation Closure-Property UGC NET CS 2017 Jan- paper-3

Question 191 Explanation:

be closed under intersection but if a language is not closing under either of union or complementation then it can or can not be closed under intersection.
So here, Statement (A) is true because regular language, context sensitive language and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable language is closed under union but not under complementation but still it is closed under intersection.
Statement (B): The meaning of given statement is that if a class of languages that is closed under union and intersection then it has to be closed under complementation but if a language is not closing under either of union or intersection then it can or can not be closed under complementation.
So here, Statement (B) is false because regular language, context sensitive language, recursive language and recursively enumerable language are closed under union and intersection but only regular language, context sensitive language and recursive language are closed under complementation , recursively enumerable language is not closing under complementation after being closed under union and intersection.
Hence statement (B) is not true.

Question 192

Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that

A	log_K\|W\| ≤ h ≤ log_K((\|W\|-1) / k-1)
B	log_K\|W\| ≤ h ≤ log_K(K\|W\|)
C	log_K\|W\| ≤ h ≤ K log_K\|W\|
D	log_K\|W\| ≤ h ≤ ((\|W\|-1) / k-1)

Theory-of-Computation Context-Free-Grammar UGC NET CS 2017 Jan- paper-3

Question 192 Explanation:

Min height of any tree is log_k |W|
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log_2 (|W|+1)
so in general it should be log_k ((|w|-1) / (k-1))

Question 193

Given the following two languages : L₁ = {aⁿ bⁿ | n ≥ 0, n ≠ 100} L₂= {w ∈ {a, b, c}*| n_a(w) = n_b(w) = n_c(w)} Which of the following options is correct ?

A	Both L₁ and L₂ are not context free language
B	Both L₁ and L₂ are context free language.
C	L₁ is context free language, L₂ is not context free language.
D	L₁ is not context free language, L₂ is context free language.

Theory-of-Computation Context-Free-Language UGC NET CS 2017 Jan- paper-3

Question 193 Explanation:

Statement 1: L1 is a context free language because we can easily construct a pushdown automata which can push all a's onto the top of stack and then when b's comes as input for each "b" one "a" will be popped up. If number of a's is equal to number of b's then final stage is reached and string is accepted except the case when 100th "b" came as input we can go to a non final state and if after that any "b" came as input then the transaction can take place to a final state according to the equal number of b's and a's else we remain on that non-final state. So in this way a pushdown automata can be constructed for given language.
Hence L1 is a context free language.
Statement 2: L2 is not a context free language because we can push a's on the top of stack and when b's came as input we can pop one "a" for each "b" so in this way stack will get empty before comparing equal number of a, b and c. For comparing number of "c" the will be no "a or b" on the top of stack.
Hence L2 is not a context free language.

Question 194

Given the following two statements :
A. L = {w|n_a(w) = n_b(w)} is deterministic context free language, but not linear.
B. L = {aⁿ bⁿ} ∪ {aⁿ b²ⁿ} is linear, but not deterministic context free language.
Which of the following options is correct ?

A	Both (A) and (B) are false.
B	Both (A) and (B) are true.
C	(A) is true, (B) is false.
D	(A) is false, (B) is true.

Theory-of-Computation Context-Free-Language UGC NET CS 2017 Jan- paper-3

Question 194 Explanation:

Statement-1:
A linear grammar is a context free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.
ex-1: S→ aSb | ab
ex-2: S→ aS | Sb | ϵ
The grammar for (a)--> S→ϵ,S→SaSbS,S→SbSaS }

which is not linear. It is DCFL
Statement-2:
The example grammar is
S→ aSb | aSbb | ϵ
Hence it is linear language and it is not DCFL.

Question 195

Which of the following pairs have different expressive power?

A	Single-tape-turing machine and multi-dimensional turing machine.
B	Multi-tape turing machine and multi-dimensional turing machine.
C	Deterministic pushdown automata and non-deterministic pushdown automata.
D	Deterministic finite automata and Non-deterministic finite automata

Theory-of-Computation Turing-machines UGC NET CS 2017 Jan- paper-3

Question 195 Explanation:

Option(A): It is incorrect option because using multi-dimensional turing machine we can speed up the process of accepting the language but it does not mean that Single-tape-turing machine can't accept the string that multidimensional turing machine accepts.

Option(B): is also incorrect because both machines are same so they can accept the same string with same speed.

Option(C) : It is correct option because Non deterministic pushdown automata is more powerful than deterministic pushdown automata because by using non-deterministic pushdown automata L= {ww | w belongs to (a,b)*} can be accepted but the same language can't be accepted using deterministic pushdown automata.

Option(D) : it is incorrect option because DFA and NDFA both are equivalent to each other i.e. we can convert DFA into NFA and NFA into DFA. DFA and NFA are equal in powers and can accept the same strings.

Question 196

Which of the following statements is false?

A	Every context-sensitive language is recursive.
B	The set of all languages that are not recursively enumerable is countable.
C	The family of recursively enumerable languages is closed under union.
D	The families of recursively enumerable and recursive languages are closed under reversal.

Theory-of-Computation Languages-and-Grammars UGC NET CS 2017 Jan- paper-3

Question 196 Explanation:

Option(A) : it is correct option because L= {aⁿ bⁿ cⁿ} is a context sensitive language and it can also be accepted by the turing machine. Hence every CSL also recursive language.

Option(B): It is incorrect option.

Option(C): Yes it is true that recursively enumerable languages are closed under union.

Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.

NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.

Question 197

The regular grammar for the language L = {aⁿb^m | n + m is even} is given by

A	S → S₁ \| S2 S₁ → a S₁\| A₁ A₁ → b A₁\| λ S₂→ aaS₂\| A₂ A₂ → b A₂\| λ
B	S → S₁\| S₂ S₁→ a S₁\| aA₁ S₂ → aaS₂ \| A₂ A₁ → b A₁\| λ A₂ → b A₂\| λ
C	S → S₁ \| S₂ S₁→ aaa S₁\| aA₁ S₂ → aaS₂\| A₂ A₁ → b A₁\| λ A₂ → b A₂\| λ
D	S → S₁ \| S₂ S₁ → aa S₁\| A₁ S₂ → aaS₂ \| aA₂ A₁ → bbA₁ \| λ A₂ → bbA \| b

Theory-of-Computation Regular-Language UGC NET CS 2016 Aug- paper-3

Question 197 Explanation:

NOTE: Here "λ" means NULL.
Option(A) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S₁
S₁ → a S₁
S₁ → aa S₁
S₁ → aaA₁
S₁ → aab A₁
S₁ → aabλ
Option(B) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S₁
S₁ → a S₁
S₁ → aaA₁
S₁ → aabA₁
S₁ → aabλ
Option(C) is not correct because it can generate strings like { aab, aaaab, aaaaaab,............}
S → S₂
S₂ → aaS₂
S₂ → aaA₂
S₂ → aabA₂| λ
S₂ → aabλ
Option(D) is correct because it generates strings like {ab, aabb, aaab,..........}

Question 198

Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is

A	{λ, a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
B	{a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
C	{w ∈ { a, b}* \| \|w\| > 3} ∪ {a, b, ab, ba}
D	{λ, a, b, ab, ba} ∪ {w ∈ {a, b}* \| \|w\| ≥ 3}

Theory-of-Computation Languages-and-Grammars UGC NET CS 2016 Aug- paper-3

Question 198 Explanation:

Complement of a language L means the complement form of given language L will contain all String except the strings that L contains.
Here L= {aa,bb}
It means complement of L can contain { λ, a, b, ab, ba, aaa, aab, aba, bba,..................}
Hence Option (D) is correct.

Question 199

Consider the following identities for regular expressions:
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true?

A	(a) and (b) only
B	(b) and (c) only
C	(c) and (a) only
D	(a), (b) and (c)

Theory-of-Computation Regular-Expression UGC NET CS 2016 Aug- paper-3

Question 199 Explanation:

The given identities are the closure properties of regular expressions. Following are few identities for regular expressions:
∅* = ε
ε* = ε
RR* = R*R
R*R* = R*
(R*)* = R*
RR* = R*R
(PQ)*P =P(QP)*
(r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)*
Hence option(D) is correct.

Question 200

Given the following two languages :
L₁ = {uww^Rν | u, v, w ∈ {a, b}⁺}
L₂ = {uww^Rν | u, ν, w ∈ {a, b}+, |u| > |ν|}
Which of the following is correct ?

A	L₁ is regular language and L₂ is not regular language.
B	L₁ is not regular language and L₂ is regular language.
C	Both L₁ and L₂ are regular languages.
D	Both L₁ and L₂ are not regular languages.

Theory-of-Computation Regular-Language UGC NET CS 2016 Aug- paper-3

Question 200 Explanation:

Question 201

Given a Turing Machine M = ({q 0 , q 1 }, {0, 1}, {0, 1, B}, δ, B, {q1 }) Where δ is a transition function de ned as δ(q 0 , 0) = (q 0 , 0, R) δ(q 0 , B) = (q 1 , B, R) The language L(M) accepted by Turing machine is given as :

A	0* 1*
B	00*
C	10*
D	10

Theory-of-Computation Turing-machines UGC NET CS 2016 Aug- paper-3

Question 201 Explanation:

Question 202

Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → ν, with |ν| = k > 1. The derivation tree for any string W ∈ L (G) has a height such that

A	h<((\|W\| - 1)/k-1)
B	log_k\|W\| < h
C	log_k\|W\| < h < ((\|W\| - 1)/k-1)
D	log_k\|W\| <= h <= ((\|W\| - 1)/k-1)

Theory-of-Computation Context-Free-Grammar UGC NET CS 2016 Aug- paper-3

Question 202 Explanation:

Min height of any tree is log_k|W|
For max height (since k>1, consider k=2) , hence it is CNF form and in CNF height is log₂|W|+1)
So, in general it should be log_k((|w|-1) / (k-1))

Question 203

The regular expression for the complement of the language L = {aⁿb^m|n ≥ 4, m ≤ 3} is:

A	(λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)*
B	(λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)*
C	(λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)*
D	(λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)*

Theory-of-Computation Regular-Expression UGC NET CS 2016 July- paper-3

Question 203 Explanation:

DFA for given language L is

Question 204

Consider the following two languages : L₁ = {0ⁱ1^j| gcd (i, j) = 1} L₂ is any subset of 0*. Which of the following is correct ?

A	L₁ is regular and L₂* is not regular
B	L₁ is not regular and L₂* is regular
C	Both L₁ and L₂* are regular languages
D	Both L₁ and L₂* are not regular languages

Theory-of-Computation Regular-Language UGC NET CS 2016 July- paper-3

Question 204 Explanation:

L₁ = {0ⁱ1^j| gcd (i, j) = 1}

A language could be regular if the difference between two consecutive terms is in G.P. But here L₁ does not contains the strings in G.P form. Hence it is not regular language.

L₂ is any subset of 0* because any subset of 0* could be {0}, {00}, {000}, {0000}, {0,00}, {0,00,000} ............... and we can have a finite automata which can accept all these subsets. Hence L2 is a regular language.

Question 205

Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation R_M defined by M. As all states are reachable from the start state, R_M has _____ equivalence classes.

A	2
B	4
C	5
D	6

Theory-of-Computation Finite-Automata UGC NET CS 2016 July- paper-3

Question 206

Let L = {0ⁿ1ⁿ|n ≥ 0} be a context free language. Which of the following is correct ?

A	L’ is context free and L^k is not context free for any k ≥ 1.
B	L’ is not context free and L^k is not context free for any k ≥ 1.
C	Both L’ and L^k is for any k ≥ 1 are context free.
D	Both L’ and L^k is for any k ≥ 1 are not context free.

Theory-of-Computation Context-Free-Language UGC NET CS 2016 July- paper-3

Question 207

Given a Turing Machine M = ({q₀, q₁, q₂, q₃}, {a, b}, {a, b, B}, δ, B, {q₃}) Where δ is a transition function defined as δ(q₀, a) = (q₁, a, R) δ(q₁, b) = (q₂, b, R) δ(q₂, a) = (q₂, a, R) δ(q₃, b) = (q₃, b, R) The language L(M) accepted by the Turing Machine is given as:

A	aa*b
B	abab
C	aba*b
D	aba*

Theory-of-Computation Turing-machines UGC NET CS 2016 July- paper-3

Question 207 Explanation:

Question 208

The family of context sensitive languages is __________ under union and __________ under reversal.

A	closed, not closed
B	not closed, not closed
C	closed, closed
D	not closed, closed

Theory-of-Computation Languages-and-Grammars UGC NET CS 2015 Dec - paper-3

Question 208 Explanation:

Context sensitive languages are closed under union, intersection, complement, concatenation, kleene star, ϵ-free Homomorphism, substitution( ϵ-free), inverse homomorphism, reverse, intersection with regular language.
Hence the correct option is (C)

Question 209

Match the following:

A	(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
B	(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
C	(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
D	(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)

Theory-of-Computation Languages-and-Grammars UGC NET CS 2015 Dec - paper-3

Question 209 Explanation:

{aⁿ bⁿ|n > 0} is a deterministic context free language but not regular because the given language requires a storing device and finite state machine does not contain any storing device. {aⁿ bⁿ|n > 0} can be accepted by a pushdown automata by pushing all the a’s on top of stack and when b’s come as input pop one “a” for each “b”.
The given language {aⁿbⁿ a^{n.^{| n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly.

Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation

{aⁿ bⁿ aⁿ} is context sensitive language but not context free language, the logic is the same as above. SInce for given language can’t be accepted by pushdown automata, so it is not a context free language.}}

Question 210

The language of all non-null strings of a’s can be defined by a context free grammar as follows: S → aS|Sa|a The word a³ can be generated by __________ different trees.

A	two
B	three
C	four
D	five

Theory-of-Computation Context-Free-Grammar UGC NET CS 2015 Dec - paper-3

Question 210 Explanation:

Question 211

The context free grammar given by
S → XYX
X → aX|bX|λ
Y → bbb
generates the language which is defined by regular expression:

A	(a + b)*bbb
B	abbb(a + b)*
C	(a + b)(bbb)(a + b)
D	(a + b)(bbb)(a + b)*

Theory-of-Computation Context-Free-Grammar UGC NET CS 2015 Dec - paper-3

Question 211 Explanation:

Option(a) is not correct because S → XYX, Y → bbb it means the regular expression for given grammar will contain "bbb" in between.
Option(B) is incorrect because "bbbb(a+b)* can also be generated by given grammar.
Option (C) is correct because S → XYX X → aX|bX|λ Y → bbb , here "bbb" will be in middle and X → aX|bX|λ can generate (a+b)* and since S → XYX is having "X" before and after "Y" so it is correct.
Option (D) is not correct because X → aX|bX|λ can generate (a+b)^* and since S → XYX is having "X" before and after "Y" so we can have (a+b)* before and after "bbb"

Question 212

There are exactly __________ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.

A	64
B	56
C	1024
D	5832

Theory-of-Computation Finite-Automata UGC NET CS 2015 Dec - paper-3

Question 212 Explanation:

Question 213

Given the following two languages: L₁ = {aⁿb aⁿ|n > 0} L₂ = {aⁿ b aⁿb^{n + 1}|n > 0} Which of the following is correct ?

A	L₁is context free language and L₂is not context free language
B	L₁is not context free language and L₂is context free language
C	Both L₁ and L₂are context free languages
D	Both L₁ and L₂are not context free languages

Theory-of-Computation Context-Free-Language UGC NET CS 2015 Dec - paper-3

Question 213 Explanation:

L1 is CFL because we can push all a's first on the top of stack when a "b" come as input change the state and don't push "b" on stack now when "a" comes after "b" then for each "a" pop one "a" from top of stack.
L2 is not CFL because we can push all a's first on the top of stack when a "b" come as input change the state and don't push "b" on stack now when "a" comes after "b" then for each "a" pop one "a" from top of stack. . Bur for "b" that comes in last we don't have "a" to compare them. So it is not CFL language.

There are 213 questions to complete.

A	{a^mbⁿ \| n>=m, m>0}
B	{a^mbⁿ \| n>=m, m>=0}
C	{a^mbⁿ \| n>m, m>0}
D	{a^mbⁿ \| n>m, m>=0}

A	abb
B	ab
C	b*b
D	bab