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

Q. Given the recursively enumerable language (LRE), the context sensitive language (LCS) the recursive language (LREC) the context free language (LCF) and deterministic context free language (LDCF) The relationship between these families is given by

View solution

Q. Match the following:

       List- I                                                List -II
a. Context free grammar               i. Linear bounded automaton
b. Regular grammar                     ii. Pushdown automaton
c. Context sensitive grammar     iii. Turing machine
d. Unrestricted grammar             iv. Deterministic finite automaton

code:
a   b    c    d

View solution

Q. According to pumping lemma for context free languages:
Let L be an infinite context free language, then there exists some positive integer m such that any w ∈ L with I w I ≥ m can be decomposed as w = u v x y z

View solution

Q. The equivalent production rules corresponding to the production rules

S → Sα1 | Sα2 | β1 | β2 

View solution

Q. If all the production rules have single non - terminal symbol on the left side, the grammar defined is :

View solution