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

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

View solution

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 :

View solution

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

View solution

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?

View solution

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?

View solution

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

View solution

Q. Given the following two grammars :

G1 :     S → AB | aaB

A → a | Aa

B → b

G2: S→ aSbS|bSaS|λ

Which statement is correct ?

View solution

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

View solution

Q. Given the following two languages :

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

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

Which statement is correct ?

View solution

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

View solution

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:

View solution

Q. Which of the following is FALSE ?

View solution

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

View solution

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?

View solution