Test: DPDA & Context Free Languages - Computer Science Engineering (CSE) MCQ

 Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and non terminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are some languages that cannot be described by context-free grammars, but can be described by CSG.

 V is the set of non terminal symbols while T is the st of terminal symbols, their intersection would always be null.

 Here the production P is from the definition of Context free grammar and thus, has no right or left context.

The grammar with right recursive production is known as Right recursive grammar. Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.

Example: For any grammar, productions be:
S->AB
A->aaA| ^
B->Bb| ^
The partial derivation tree can be drawn as:

The grammar for the same language can be stated as :
(1) S → aMb
(2) M → A
(3) M → B
(4) A → e
(5) A → aA
(6) B → e
(7) B → bB

The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.

A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string generated by the grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string generated in the grammar.

None.