Q. Consider the following statements :

I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.

Which of the above statements are true ?

View solution

Q. Given the following statements :

(i) The power of deterministic finite state machine and nondeterministic finite state machine are same.
(ii) The power of deterministic pushdown automaton and nondeterministic pushdown automaton are same.

Which of the above is the correct statement(s) ?

View solution

Q. Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.
(ii) There is a recursive language that is not context sensitive.

View solution

Q. Which one of the following is not a Greibach Normal form grammar?

(i)            S ->a|bA|aA|bB
A->a
B->b
(ii)           S->a|aA|AB
A->a
B->b
(iii)          S->a|A|aA
A->a

View solution

Q. The equivalent grammar corresponding to the grammar G:S→aA,A→BB,B→aBb∣εG:S→aA,A→BB,B→aBb∣ε is

View solution

Q. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

View solution

Q. The following CFG

S->aB|bA, A->a|as|bAA, B->b|bs|aBB

generates strings of terminals that have

View solution

Q. Match the following :

(i) Regular Grammar                           (a) Pushdown automaton
(ii) Context free Grammar                   (b) Linear bounded automaton
(iii) Unrestricted Grammar                  (c) Deterministic finite automaton
(iv) Context Sensitive Grammar        (d) Turing machine
     
(i)   (ii)   (iii)  (iv)

View solution

Q. Which one of the following statement is false?

View solution

Q. Which of the following grammar is LR (1)?

View solution

Q. Context-free Grammar (CFG) can be recognized by

View solution

Q. A context free grammar is:

View solution

Q. Let e: B˄m→B˄n is a group code. The minimum distance of ‘e’ is equal to:

View solution

Q. A WFF that is equivalent to the WFF x=>y is:

View solution

Q. The regular expression given below describes:

r=(1+01)*(0+λ)

View solution

Q. Which of the following language is regular?

View solution

Q. Which of the regular expressions corresponds to this grammar ?

S → AB / AS, A → a / aA, B → b

View solution

Q. Which of the following strings is in the language defined by grammar S→0A, A→1A/0A/1

View solution

Q. The logic of pumping lemma is a good example of:

View solution

Q. Let A = {x | -1< x< 1} = B. The function f(x)=x/2 from A to B is:

View solution