The finite automata is called NFA when their exist ________________for a specific input from the current state to the next.

• Single path

• multiple path

• only two paths

• none

The Language described by the regular expression(0+1)*0(0+1)*0(0+1)* is the set of

• All string containing atleast two 1's

• All string containing atleast two 0's

• All string that begin and end with either 0's or 1's

• All string containing a substring 00

L1=Φ and L2={a} are the two languages. Out the following four options the one that represents L1 L2* υ L1* is

• Φ

• a*

• ε

• {ε, a}

Given a Turing Machine

M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3})

Where δ is a transition function defined as

δ(q0,a) = (q1,a,R)
δ(q1,b) = (q2,b,R)
δ(q2,a) = (q2,a,R)
δ(q2,b) = (q3,b,R)

The language L(M) accepted by the Turing Machine is given as:

• 
  

  aa*b

• abab

• aba*b

• aba*

The context free grammar given by

S→XYX
X→aX|bX|λ
Y→bbb

generates the language which is defined by regular expression:

• 
  (a+b)*bbb

• abbb(a+b)*

• (a+b)*(bbb)(a+b)*

• (a+b)(bbb)(a+b)*

The number of states in a minimal deterministic finite automaton corresponding to the language L = { aⁿ | n≥4 } is

• 3

• 4

• 5

• 6

Given the following productions of a grammar :

S→ aA| aBB;
A→aaA |λ ;
B→ bB| bbC;
C→ B

Which of the following is true ?

• The language corresponding to the given grammar is a set of even number of a’s.

• The language corresponding to the given grammar is a set of odd number of a’s.

• The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b’s.

• The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b’s.

Non-deterministic pushdown automaton that accepts the language generated by the grammar:

S→aSS | ab is

(A) δ(q0, λ, z) = { (q1, z)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, B) = { (q1, λ)},
δ(q1, λ, z) = { (qf, λ)}

(B) δ(q0, λ, z) = { (q1, Sz)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, B) = { (q1, λ)},
δ(q1, λ, z) = { (qf, λ)}

(C) δ(q0, λ, z) = { (q1, Sz)};
δ(q0, a, S) = { (q1, S)}, (q1, B) }
δ(q0, b, λ) = { (q1, B)},
δ(q1, λ, z) = { (qf, λ)}

(D) δ(q0, λ, z) = { (q1, z)};
δ(q0, a, S) = { (q1, SS)}, (q1, B) }
δ(q0, b, λ) = { (q1, B)},
δ(q1, λ, z) = { (qf, λ)}

• A

• B

• C

• D

Given the production rules of a grammar G1 as

S1→AB | aaB
A→a | Aa
B→b

and the production rules of a grammar G2 as

S2→aS2bS2 | bS2aS2 | λ

Which of the following is correct statement?

• G1 is ambiguous and G2 is not ambiguous

• G1 is ambiguous and G2 is ambiguous

• G1 is not ambiguous and G2 is ambiguous

• G1 is not ambiguous and G2 is not ambiguous

The regular expression for the following DFA is

• ab*(b + aa*b)*

• a*b(b + aa*b)*

• a*b(b* + aa*b)

• a*b(b + aab)*