Skip to content

Language#

Name Symbol Example
Alphabet Σ a,b
Word W := abba, ba, bbb...
Language L := ba babb aab

Production Rules: S → aS

Chomsky-Hierarchy#

The chomsky hierarchy classifies languages.

  • Chomsky 0: At least one non-terminal on the left α → β

  • Chomsky 1 (= context sensitive): More or equal symbols on the right than on the left. Thus, a word cannot become shorter by applying a production step αAβ → αγβ

  • Chomsky 2 (context free): Exactly one non-terminal on the left, nothing else Thus, a production rule does not depend on previous symbols A → γ

  • Chomsky 3 (regular): only one symbol on the left and the right. A → a | A → B

Backus--Naur Form (BNF)#

The Backus--Naur Form is a common notation technique for context-free grammars.

{{ FOLDER_TOC }}