Theory of Automata
Regular and context-free languages
Q.

Match the following:

List - IList - 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

codes:

 (a)(b)(c)(d)
(A)(ii)(iv)(iii)(i)
(B)(ii)(iv)(i)(iii)
(C)(iv)(i)(ii)(iii)
(4)(i)(iv)(iii(ii)
A.  

A

 B.  

B

 C.  

C

 D.  

D
Similar Questions
1.

The entity which generate Language is termed as:
A.  

Automata

 B.  

Tokens

 C.  

Grammer

 D.  

Data
2.

Production Rule: aAb->agb belongs to which of the following category?
A.  

Regular Language

 B.  

Context free Language

 C.  

Context Sensitive Language

 D.  

Recursively Ennumerable Language
3.

Which of the following statement is false?
A.  

Context free language is the subset of context sensitive language

 B.  

Regular language is the subset of context sensitive language

 C.  

Recursively ennumerable language is the super set of regular language

 D.  

Context sensitive language is a subset of context free language
4.

The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
A.  

Accepting State

 B.  

Starting Variable

 C.  

Sensitive Grammar

 D.  

None of these
5.

Which among the following cannot be accepted by a regular grammar ?
A.  

L is a set of numbers divisible by 2

 B.  

L is a set of binary complement

 C.  

L is a set of string with odd number of 0

 D.  

L is a set of 0n1n
6.

Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
A.  

V

 B.  

S

 C.  

(V+∑)*

 D.  

V+ ∑
7.

For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
A.  

Non regular language

 B.  

0n1n | n>=0

 C.  

0n1n | n>=1

 D.  

None of the mentioned
8.

The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
A.  

3

 B.  

7

 C.  

5

 D.  

6
9.

Which of the following statement is correct?
A.  

All Regular grammar are context free but not vice versa

 B.  

All context free grammar are regular grammar but not vice versa

 C.  

Regular grammar and context free grammar are the same entity

 D.  

None of the mentioned
10.

Are ambiguous grammar context free?
A.  

Yes

 B.  

No
THEORY OF AUTOMATA TOPICS