Q. Let L be a set accepted by a non deterministic 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

View solution

Q. The grammar ‘G1’

S ---> OSO| ISI | 0|1|∈

and the grammar  ‘G2’ is
S ---> as |asb| X,
X -----> Xa | a.

Which is the correct statement ?

View solution

Q. Which of the following regular expression identities are true ?

View solution

Q. The minimum number of states of the non-deterministic finite automation which accepts the language
{a b a bn| n  ≥  0} ∪ {a b an|n  ≥ 0} is 

View solution

Q. Which of the following definitions generates the same Language as L, where
L = {WWR | W ∈ {a, b}*} 

View solution

Q. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length 

View solution

Q. Given the following statements :

S1: SLR uses follow information to guide reductions.In case of LR and LALR parsers, the look-aheads are associated with the  Items and they make use of the left context available to the parser.
S2: LR grammar is a larger sub-class of context free grammar as compared to that SLR and LALR grammars. 

Which of the following is true ? 

View solution

Q. The context free grammar for the language

L= {anbm  | n ≤ m+3,n ≥ 0 ,m≥ 0 } : is

View solution

Q. Given the following statements:

S1: If L is a regular language then the language {uv | u ∈  L, v ∈ LR } is also regular.
S2: L = {wwR} is regular language.

Which of the following is true?

View solution

Q. Given the following statements.

S1: The grammars S → asb | bsa |ss I a and s→ asb | bsa| a are not equivalent.
S2: The grammars S→. ss| sss | asb | bsa| λ and S → ss |asb |bsa| λ are equivalent.

Which of the following is true?

View solution

Q. Pumping -lemma for context-free languages states :
Let Lbe an infinite context free language. Then there exists some positive integer m such that any w ∈ L with Iwl ≥m can be decomposed as w = uv xy Z with Ivxyl_________ and Ivy I such that uvz, xyZ
Z ∈ L for all z = 0, 1,2, .......

View solution

Q. The Greibach normal form grammar for the language L = {an bn+1 | n ≥ 0 } is

View solution

Q. Given the following statements:

S1: Every context-sensitive language L is recursive.
S2: There exists a recursive language that is not context sensitive.

Which statement is correct?

View solution

Q. Shift-Reduce parsers perform the following :

View solution

Q. The following Context-Free Grammar (CFG) :

S → aB | bA

A → a | as | bAA

B → b | bs | aBB

will generate

View solution

Q. Which of the following is true?

View solution

Q. The pushdown automation M = ( {q0, q1, q2}',{a, b}, {0, 1}, δ, q0,0, {q0}) with

δ (q0, a, 0) = {(q1,10)}

δ (q1,a, 1) = {(q1,11)}

δ (q1,b, 1) = {(q2 , λ)}

δ(q2 , b, 1) = {(q2 , λ)}

δ (q2 , A, 0) = {(q0, λ)}

Accepts the language

View solution

Q. Given two languages:

L1= {(ab)n,ak I n> k, k >=0}

L2 = {an bm l n ≠ m}

Using pumping lemma for regular language, it can be shown that

View solution

Q. Regular expression for the complement of language L = {a^n b^m I n ≥ 4, m ≤ 3} is

View solution

Q. We can show that the clique problem is NP-hard by proving that

View solution