Theory-of-Computation

Question 1

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?

A
(a* + b* + c*)*
B
(a*b*c*)*
C
((ab)* + c*)*
D
(a*b* + c*)*
       Theory-of-Computation       Regular-Expressions       GATE 2004-IT
Question 1 Explanation: 
With the given r.e. (a+b+c)* we can generate “a”.
From option ‘c’ we cannot be able to create a without b. So option is not equivalent.
Question 2

Which one of the following statements is FALSE?

A
There exist context-free languages such that all the context-free grammars generating them are ambiguous
B
An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it
C
Both deterministic and non-deterministic pushdown automata always accept the same set of languages
D
A finite set of string from one alphabet is always a regular language
       Theory-of-Computation       General       GATE 2004-IT
Question 2 Explanation: 
Deterministic automata can be able to recognize all the deterministic context-free languages.
But non-deterministic ones can recognize all context-free languages.
So, option C is false.
Question 3

Which one of the following strings is not a member of L(M)?
Let M = (K,Σ,Γ,Δ,s,F) be a pushdown automaton, where
K = {s,f}, F = {f}, Σ = {a,b}, Γ = {a} and
Δ = {((s,a,ε), (s,a)), ((s,b,ε), (s,a)), ((s,a,ε), (f,ε)), ((f,a,a), (f,ε)), ((f,b,a), (f,ε))}

A
aaa
B
aabab
C
baaba
D
bab
       Theory-of-Computation       Push-Down-Automata       GATE 2004-IT
Question 3 Explanation: 
First let’s draw PDA,

Now, here transition ((s,a,t), (s,a)) implies reading input symbol ‘a’ in the state ‘s’ we have to move ‘s’ having any symbol on the top of stack … epsilon here implies “anything on of Top of stack”.
Now, observe the PDA carefully, it is saying that in the starting you have to push one ‘a’ for each of ‘a’ and ‘b’. And in the end you have to pop one ‘a’ by one ‘a’ by one ‘a’ or one ‘b’. Thus the count of a’s and b’s in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one ‘a’, i.e., moving from s to f.
So, all odd strings in which ‘a’ is the middle element will be accepted.
Thus in our question, option (B) is aabab having ‘b’ in the middle and thus can’t be accepted.
Question 4

Let M = {K,Σ,δ,s,F} be a finite state automaton, where
K = {A,B}, Σ = {a,b}, s = A, F = {B}, δ(A,a) = A, δ(A,b) = B, δ(B,a) = B and δ(B,a) = A
A grammar to generate the language accepts by M can be specified as G = (V,Σ,R,S), where V = K∪Σ, and S = A.
Which one of the following set to rules will make L(G) = L(M)?

A
{A→aB, A→bA, B→bA, B→aA, B→ε}
B
{A→aA, A→bB, B→bB, B→aA, B→ε}
C
{A→bB, A→aB, B→aA, B→bA, A→ε}
D
{A→aA, A→bA, B→bB, B→aA, A→ε}
       Theory-of-Computation       Finite-Automata       GATE 2004-IT
Question 5

Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.

    I. L is deterministic context-free.
    II. L is context-free but not deterministic context-free.
    III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

A
II only
B
III only
C
I only
D
I and III only
       Theory-of-Computation       Languages-and-Grammars       GATE 2020       Video-Explanation
Question 5 Explanation: 
L is DCFL.
We can make DPDA for this.

L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 6

Consider the following statements.

    I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
    II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

A
Both I and II
B
II only
C
Neither I nor II
D
I only
       Theory-of-Computation       Regular-Language       GATE 2020       Video-Explanation
Question 6 Explanation: 
Statement I is wrong.
Assume L1 = {an bn | n>0} and L2 = complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular, L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1 = {ab}
L2 = {aabb}
L3 = {aaabbb}
.
.
.
L100 = {a100 b100}
.
.
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……}
then we will get a new language L = {an bn | n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 7

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

A
10*(0*10*10*)*
B
((0 + 1)*1(0 + 1)*1)*10*
C
(0*10*10*)*10*
D
(0*10*10*)*0*1
       Theory-of-Computation       Regular-Expression       GATE 2020       Video-Explanation
Question 7 Explanation: 
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 8

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

    L1 = | L(M) = Φ}
    L2 = {| M on input w reaches state q in exactly 100 steps}
    L3 = {| L(M) is not recursive}
    L4 = {| L(M) contains at least 21 members}
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2020       Video-Explanation
Question 8 Explanation: 
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 9

Consider the following language. 

   L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}

The minimum number of states in a DFA that accepts L is ______.

A
6
       Theory-of-Computation       Finite-Automata       GATE 2020       Video-Explanation
Question 9 Explanation: 
DFA 1: No. of a’s divisible by 2.

DFA 1: No. of a’s not divisible by 3

Using product automata:
Question 10

Consider the following languages.

    L1 = {wxyx | w,x,y ∈ (0 + 1)+}
    L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?

A
L1 is context-free but not regular and L2 is context-free.
B
Neither L1 nor L2 is context-free.
C
L1 is regular and L2 is context-free.
D
L1 is context-free but L2 is not context-free.
       Theory-of-Computation       Languages-and-Grammars       GATE 2020       Video-Explanation
Question 10 Explanation: 
L1 is regular. y can be expanded and w can also expanded. So x can be either “a” or “b”.
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 11
Which one of the following regular expressions correctly represents the language of the finite automaton given below?
A
ab*bab* + ba*aba*
B
(ab*b)*ab* + (ba*a)*ba*
C
(ab*b + ba*a)* (a* + b*)
D
(ba*a + ab*b)* (ab* + ba*)
       Theory-of-Computation       Regular-Expression       GATE 2022       Video-Explanation
Question 11 Explanation: 
Regular expression ab*bab* +ba*aba* does not generate the string “abb” which is accepted by FA hence this is not true.
(ab*b)*ab*+(ba*a)*ba* does not generate the string “abbaa” hence this is also wrong.
(ab*b+ba*a)*(a*+b*) generates epsilon hence this is also wrong.
(ab*b+ba*a)*(ab*+ba*) is the correct regular expression.
GATE 2022 Computer Science and Information Technology (CS)
Question 12
Which of the following statements is/are TRUE?
A
Every subset of a recursively enumerable language is recursive.
B
If a language L and its complement L’ are both recursively enumerable, then L must be recursive.
C
Complement of a context-free language must be recursive.
D
If L1 and L2 are regular, then L1 ∩ L2 must be deterministic context-free
       Theory-of-Computation       Languages-and-Grammars       GATE 2022       Video-Explanation
Question 12 Explanation: 
Every subset of recursively enumerable need not be recursive. For example (a+b)* is a universal language and regular. Every language over alphabet {a,b} is subset of (a+b)*. This language is regular so it is recursively enumerable also and so many languages are known to be non-recursive which are definitely subset of (a+b)*. Thus every subset of recursively enumerable need not be recursive.
If L and L(complement) both are recursively enumerable then L must be recursive. It is a theorem.
Every CFL is CSL and CSL is closed under complement so complement of CFL must be CSL and every CSL is recursive. Thus the complement of CFL must be CSL, hence it must be recursive also.
If L1 and L2 are regular then their intersection must be regular, as regular languages are closed under intersection, so L1 intersection L2 must be regular, hence it must be DCFL, since every regular is also a DCFL.
Question 13
Which of the following is/are undecidable?
A
Given two Turing machines M1 and M2, decide if L(M1)=L(M2).
B
Given a Turing machine M, decide if L(M) is regular.
C
Given a Turing machine M, decide if M accepts all strings.
D
Given a Turing machine M, decide if M takes more than 1073 steps on every string.
       Theory-of-Computation       Turing-machines       GATE 2022       Video-Explanation
Question 13 Explanation: 
Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Question 14
A
L 1 and L 2 are regular.
B
L 1 and L 2 are context-free.
C
L 1 is regular and L 2 is context-free.
D
L 1 and L 2 are context-free but not regular.
       Theory-of-Computation       Context-Free-Language       GATE 2022       Video-Explanation
Question 14 Explanation: 
Both L1 and L2 are regular.
Since no condition on the value of “n” is mentioned so for a particular case we can assume n=0, now when n=0 the language L1= w =(a+b)*
So if one case is (a+b)* then now even we assume any value of “n” the generated string will already present in (a+b)* thus L1=(a+b)*.
L2: In L2 the middle X can expand and consume all symbols of w except the first symbol and symbols of wr except the last symbol so L2 will be equivalent to language all strings start and end with the same symbol, hence L2 is regular.
Question 15
Consider the following languages:
A
L 1 is not context-free but L 2 and L 3 are deterministic context-free.
B
Neither L 1 nor L 2 is context-free.
C
D
Neither L 1 nor its complement is context-free.
       Theory-of-Computation       Context-Free-Language       GATE 2022       Video-Explanation
Question 15 Explanation: 
L1=ww is a well-known CSL (non-CFL) and its complement is CFL.
L2={an bn cm | m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn | m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn | n >=0} so this is CSL (non-CFL).
So A is a true statement and rest all are false statements.
Question 16

Which two of the following four regular expressions are equivalent? (ε is the empty string).

    (i) (00)*(ε+0)
    (ii) (00)*
    (iii) 0*
    (iv) 0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
       Theory-of-Computation       Regular-Expressions       GATE 1996
Question 16 Explanation: 
(00)*(ε+0),0*
In these two, we have any no. of 0’s as well as null.
Question 17

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
       Theory-of-Computation       Decidability-and-Undecidability       GATE 1996
Question 17 Explanation: 
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Question 18

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

A
L = {x|x has an equal number of a’s and b’s } is regular
B
L = {anbn|n≥1} is regular
C
L = {x|x has more a’s and b’s} is regular
D
L = {ambn|m ≥ 1, n ≥ 1} is regular
       Theory-of-Computation       Identify-Class-Language       GATE 1996
Question 18 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So ‘L’ Is Regular.
Question 19

If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

A
L1, L2
B
L1 ∩ L2
C
L1 ∩ R
D
L1 ∪ L2
       Theory-of-Computation       Identify-Class-Language       GATE 1996
Question 19 Explanation: 
Context free languages are not closed under intersection.
Question 20

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
D
None of the above
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 20 Explanation: 
(B) is the answer. Because for any binary string of 0’s and 1’s we can append another string to make it contain equal no. of 0’s and 1’s, i.e., any string over {0,1} is a prefix of a string in L.
Question 21

The grammar whose productions are 

  → if id then 
  → if id then   else 
  → id := id

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 21 Explanation: 
We have to generate
“if a then if b then c:=d else c:=f”.
Parse tree 1:

Parse tree 2:
Question 22

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

A
4
B
3
C
2
D
1
       Theory-of-Computation       Finite-Automata       GATE 1996
Question 22 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 23

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below. 

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G’ that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

A
Theory Explanation.
       Theory-of-Computation       Context-Free-Grammar       GATE 1996
Question 24

Let Q = ({q1,q2}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents. 

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)}
A
Theory Explanation.
       Theory-of-Computation       Push-Down-Automata       GATE 1996
Question 25

Given Σ = {a,b}, which one of the following sets is not countable?

A
Set of all strings over Σ
B
Set of all languages over Σ
C
Set of all regular languages over Σ
D
Set of all languages over Σ accepted by Turing machines
       Theory-of-Computation       Countability       GATE 1997
Question 25 Explanation: 
Uncountable: Set of all languages over Σ is uncountable.
Question 26

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

A
0*(1+0)*
B
0*1010*
C
0*1*01
D
0(10+1)*
       Theory-of-Computation       Regular-Expressions       GATE 1997
Question 26 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn’t generate 1.
(D) answer.
Question 27

Which one of the following is not decidable?

A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
       Theory-of-Computation       Decidability-and-Undecidability       GATE 1997
Question 27 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number ‘k’ and simulating a TM for ‘k’ steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM’s is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 28

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata? 

 Note: wR  is the string obtained by reversing 'w'.
A
{w⊂wR|w ∈ {a,b}*}
B
{wwR|w ∈ {a,b,c}*}
C
{anbncn|n ≥ 0}
D
{w|w is a palindrome over {a,b,c}}
       Theory-of-Computation       Push-Down-Automata       GATE 1997
Question 28 Explanation: 
(A) w⊂wR, can be realized using DPDA because we know the center of the string that is c here.
(B) wwR, is realized by NPDA because we can’t find deterministically the center of palindrome string.
(C) {anbncn | n ≥ 0} is CSL.
(D) {w | w is palindrome over {a,b,c}},
is realized by NPDA because we can’t find deterministically the center of palindrome string.
Question 29

If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?

A
A ⊂ B
B
B ⊂ A
C
A and B are incomparable
D
A = B
       Theory-of-Computation       Regular-Expressions       GATE 1998
Question 29 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 30

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

A
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary
B
The numbers 1, 2, 4, ………………., 2n, …………..written in unary
C
The set of binary string in which the number of zeros is the same as the number of ones
D
The set {1, 101, 11011, 1110111, ………..}
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 30 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 …. = 10*
which is regular and recognized by deterministic finite automata.
Question 31

Regarding  the power of recognition of languages, which of the following statements is false?

A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
D
Both B and C
       Theory-of-Computation       NFA       GATE 1998
Question 31 Explanation: 
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
Question 32

The string 1101 does not belong to the set represented by

A
110*(0 + 1)
B
1 ( 0 + 1)* 101
C
(10)* (01)* (00 + 11)*
D
Both C and D
       Theory-of-Computation       Regular-Expressions       GATE 1998
Question 32 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 33

How many sub strings of different lengths (non-zero) can be found formed from a character string of length n?

A
n
B
n2
C
2n
D
       Theory-of-Computation       Sub-Strings       GATE 1998
Question 33 Explanation: 
Let us consider an example S = {APB}
Possible sub-strings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 34

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is

A
2
B
5
C
8
D
3
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 34 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 35

Which of the following statements is false?

A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
       Theory-of-Computation       Regular-Language       GATE 1998
Question 35 Explanation: 
Let regular language L = a*b* and subset of L is anbn, n ≥ 0, which is not regular. Hence option (B) is false.
Question 36

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}* | w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}

A
Theory Explanation.
       Theory-of-Computation       DFA       GATE 1998
Question 37

Let M = ({q0, q1}, {0, 1}, {z0, x}, δ, q0, z0, ∅) be a pushdown automaton where δ is given by

    δ(q0, 1, z0) = {(q0, xz0)}
    δ(q0, ε, z0) = {(q0, ε)}
    δ(q0, 1, X) = {(q0, XX)}
    δ(q1, 1, X) = {(q1, ε)}
    δ(q0, 0, X) = {(q1, X)}
    δ(q0, 0, z0) = {(q0, z0)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

A
Theory Explanation.
       Theory-of-Computation       Push-Down-Automata       GATE 1998
Question 38

(a) Let G1 = (N, T, P, S1) be a CFG where,
N = {S1, A, B}, T = {a,b} and
P is given by 

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a

What is L(G1)?

(b) Use the grammar in part(a) to give a CFG
for L2 = {ai bj ak bl | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L2 inherently ambiguous?

A
Theory Explanation.
       Theory-of-Computation       Context-Free-Grammar       GATE 1998
Question 39

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions 

Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε
A
Theory Explanation.
       Theory-of-Computation       Regular-Expression       GATE 1998
Question 40

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains

A
n states
B
n + 1 states
C
n + 2 states
D
None of the above
       Theory-of-Computation       Finite-Automata       GATE 1999
Question 40 Explanation: 
Let’s draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Question 41

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
       Theory-of-Computation       Context-Free-Language       GATE 1999
Question 41 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 42

Let LD be the set of all languages accepted by a PDA by final state and LE the set of all languages accepted by empty stack. Which of the following is true?

A
LD = LE
B
LD ⊃ LE
C
LE = LD
D
None of the above
       Theory-of-Computation       Push-Down-Automata       GATE 1999
Question 42 Explanation: 
For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.
Question 43

If L is context free language and L2 is a regular language which of the following is/are false?

A
L1 – L2 is not context free
B
L1 ∩ L2 is context free
C
~L1 is context free
D
~L2 is regular
E
Both A and C
       Theory-of-Computation       Identify-Class-Language       GATE 1999
Question 43 Explanation: 
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 – L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 – L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection. So True.
(C) CFL is not closed under complementation. Hence False.
(D) Regular language is closed under complementation.
Hence True.
Question 44

A grammar that is both left and right recursive for a non-terminal, is

A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or unambiguous
D
None of the above
       Theory-of-Computation       Grammar       GATE 1999
Question 44 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 45

(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)

A
Theory Explanation.
       Theory-of-Computation       Regular-Language       GATE 1999
Question 46

Show that the language L = {xcx| x ∈ {0,1}* and c is a terminal symbol} is not context free, c is not 0 or 1.

A
Theory Explanation.
       Theory-of-Computation       Context-Free-Language       GATE 1999
Question 47

Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

A
S ⊂ T
B
T ⊂ S
C
S = T
D
S ∩ T = ɸ
       Theory-of-Computation       Regular-Expressions       GATE 2000
Question 47 Explanation: 
If we draw DFA for language S and T it will represent same.
Question 48

Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?

A
L = 0+
B
L is regular but not 0+
C
L is context free but not regular
D
L is not context free
       Theory-of-Computation       Identify-Class-Language       GATE 2000
Question 48 Explanation: 
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
Question 49

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

A
L must be {an |n is odd}
B
L must be {an |n is even}
C
L must be {an|≥0}
D
Either L must be {an |n is odd}, or L must be {an | n is even}
       Theory-of-Computation       Finite-Automata       GATE 2000
Question 49 Explanation: 
If first state is final, then it accepts even no. of a’s. If second state is final then it accepts odd no. of a’s.
Question 50

Consider the following decision problems:

    (P1) Does a given finite state machine accept a given string
    (P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?

A
Both (P1) and (P2) are decidable
B
Neither (P1) nor (P2) are decidable
C
Only (P1) is decidable
D
Only (P2) is decidable
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2000
Question 50 Explanation: 
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content