Theory of computation

“Context Free Grammar-Derivations and Definitions”.

1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
Answer: c

Explanation: The entity which accepts a language is termed as Automata while the one
which generates it is called Grammar. Tokens are the smallest individual unit of a
program.


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
Answer: c

Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non
deterministic Language has the production rule where the production is context
dependent i.e. aAb->agb.


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
Answer: d

Explanation: Every regular language can be produced by context free grammar and
context free language can be produced by context sensitive grammar and so on.