adplus-dvertising
frame-decoration

Question

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

a.

 ii    iv   iii    i

b.

ii    iv    i    iii

c.

iv    i     ii    iii

d.

i    iv   iii    ii

Answer: (b).ii    iv    i    iii

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Match the following:        List- I                                                List -II a. Context free grammar               i. Linear bounded automaton b. Regular...

Similar Questions

Discover Related MCQs

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

Q. The equivalent production rules corresponding to the production rules

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

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

Q. Minimal deterministic finite automaton for the language L = {0n | n ≥ 0 , n ≠ 4} will have

Q. The regular expression corresponding to the language L where L = { x ∈{0, 1}* | x ends with 1 and does not contain substring 00 } is :

Q. A context free grammar for L = { w | n0 (w) > n1 (w)} is given by :

Q. Given the following two statements :

S1: If L1 and L2 are recursively enumerable languages over Σ, then L1 ⋃ L2 and L1 ⌒ L2 are also recursively enumerable.

S2: The set of recursively enumerable languages is countable.

Which of the following is correct?

Q. Given the following grammars :

G1: S → AB|aaB

A → aA | ∈

B → bB | ∈

G2: S → A | B

A → a A b | ab

B → a b B | ∈

Which of the following is correct?

Q. Let L be any language. Define even (W)  as the  strings  obtained by extracting from W the letters in the even-numbered positions and even (L) = {even (W) | W ԑ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | v W ԑ L,with | v | = 2}.

If L is regular language then

Q. Given the following two grammars :

G1 :     S → AB | aaB

A → a | Aa

B → b

G2: S→ aSbS|bSaS|λ

Which statement is correct ?

Q. Match the following:

List-I                                                            List-II

a. Chomsky Normal form                       i.  S→ bSS|aS|c

b. Greibach Normal form                        ii.  S→ aSb|ab

c. S-grammar                                           iii. S→ AS|a

                                                                         A→ SA|b

d. |LL grammar                                        iv. S→ aBSB

                                                                         B→ b

Codes:
a       b       c       d

Q. Given the following two languages :

L1 = {anbn |n≥1} ∪ {a}

L2= {w C wR|we {a,b}*}

Which statement is correct ?

Q. The solution of the recurrence relation of T(n) = 3T ( floor (n/4) ) +  n is

Q. 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:

Q. Which of the following is FALSE ?

Q. Consider the languages L1 = ϕ, and L2 = {1}. Which one of the following represents
L1* U L2* L1* ?

Q. 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?

Q. Given the following two languages:

L1 = {a^nb^n|n≥0, n≠100}
L2 = {w ϵ {a,b,c}*| na(w) = nb(w) = nc(w)}

Which of the following options is correct?

Q. Given the following two statements:

A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} U {an b2n} is linear, but not deterministic context free language.

Which of the following options is correct?

Q. Which of the following pairs have different expressive power?