Test: Context Free Grammar Derivations & Definitions - Computer Science Engineering (CSE) MCQ

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.

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.

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

G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.

There exists no finite automata to accept the given language i.e. 0ⁿ1ⁿ. For other options, it is possible to make a dfa or nfa representing the language set.

According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.

The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}

 Regular grammar is a subset of context free grammar and thus all regular grammars are context free.

 A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.