Grammars and the Chomsky hierarchy
Terminals, non-terminals, start symbol and production rules; the language a grammar generates; the four Chomsky types with the shape of their rules, their machine and a witness language.
- 28 cards
- 3 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
A few cards from the deck
Formal grammar: what is it?
Show the answer
A quadruple made of a set of terminals, a set of non-terminals, a start symbol (the axiom) and production rules that rewrite strings of symbols.
The words of the generated language are those obtained by rewriting the axiom until only terminals remain.
What is the most precise Chomsky type of the grammar S → aSb | ε?
- Type 2, context-free
- Type 3, regular
- Type 1, context-sensitive
- Type 0, unrestricted
Show the answer
Type 2, context-free
Each rule has a single non-terminal on the left, but in aSb the non-terminal sits in the middle: that is not the type 3 shape. The generated language, aⁿbⁿ, is not regular either. Types 1 and 0 contain type 2 but are less precise.
A grammar is given by … (the letters of the words), … (the symbols to rewrite), a … and production rules.
Show the answer
A grammar is given by terminals (the letters of the words), non-terminals (the symbols to rewrite), a start symbol and production rules.
In S → aSb | ab, S is the only non-terminal and the start symbol; a and b are the terminals. A word of the language contains only terminals.
Chomsky hierarchy: what is it?
Show the answer
A ranking of grammars into four nested types, from 3 (the most restricted) to 0 (the most general), according to the shape allowed for their rules.
The higher the type number, the simpler the machine that recognises the language, but the poorer the language: type 3 ⊂ type 2 ⊂ type 1 ⊂ type 0.
Which of these rules stops a grammar from being type 3?
- S → aS
- S → aSb
- A → bA
- S → b
Show the answer
S → aSb
In type 3 at most one non-terminal may appear on the right, and only in last position. In aSb it is followed by a terminal: remembering the a would take a stack, which a finite automaton lacks.