Formal Grammars - Chomsky Hierarchy

Type-4

• Finite Enumerable Grammar (FEG)
• Finite Enumerable Language (FEL)

Memory Lookup

are defined by rules of the forms:

• 𝑆 → 𝑠𝑡𝑟𝑖𝑛𝑔-𝑜𝑓-𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙𝑠

grammar rules G:

• 𝑆 → 𝑎𝑏𝑐
• 𝑆 → 𝑎𝑏

language of G:

• 𝐿 = {𝑎𝑏𝑐, 𝑎𝑏}

Type-3

• Regular Grammar (RG)
• Regular Language (RL)

Finite-State Automaton (FSA, FA)

regular grammar is EITHER left or right regular grammar:

• right regular grammar - is defined by rules of the forms:
  • 𝐴 → 𝑎
  • 𝐴 → 𝑎𝐵
  • 𝐴 → 𝜖
• left regular grammar - is defined by rules of the forms:
  • 𝐴 → 𝑎
  • 𝐴 → 𝐵𝑎
  • 𝐴 → 𝜖

grammar rules G:

• 𝐴 → 𝑎𝐵
• 𝐵 → 𝑏𝐵
• 𝐵 → 𝑐

language of G:

• 𝐿 = { 𝑎𝑏^𝑛𝑐 | 𝑛 ≥ 0 }

Type-2

• Context Free Grammar (CFG)
• Context Free Language (CFL)

Pushdown Automata (PDA)
Finite-State Transducer (FST)

defined by rules of the form:

• 𝐴 → 𝛼

grammar rules G:

• 𝐴 → 𝑎𝐴𝑏
• 𝐴 → 𝜖

language of G:

• 𝐿 = { 𝑎^𝑛𝑏^𝑛| 𝑛 > 0 }

Type-1

• Context Sensitive Grammar (CSG)
• Context Sensitive Language (CSL)

Linear-Bounded Automaton (LBA)

defined by rules of the form:

• 𝛼𝐴𝛽 → 𝛼𝛾𝛽
• 𝐴 → 𝜖

the rule 𝐴 → 𝜖 is allowed if 𝐴 does not appear on the right side of any rule

grammar rules G:

• 𝑆 → 𝑎𝐵𝑆𝑐
• 𝑆 → 𝑎𝑏𝑐
• 𝐵𝑎 → 𝑎𝐵
• 𝐵𝑏 → 𝑏𝑏

language of G:

• L(G) = { 𝑎^𝑛𝑏^𝑛𝑐^𝑛| 𝑛 > 0 }

Type-0.5

• Recursive Grammar (RG)
• Recursive Language (RL)

recursive grammar if it contains production rules that are recursive, meaning that expanding a non-terminal according to these rules can eventually lead to a string that includes the same non-terminal again. Otherwise, it is called a non-recursive grammar

Type-0

• Recursively Enumerable Grammar (REG)
• Recursively Enumerable Language (REL)

Turing Machine (TM)

defined by rules of the form:

• 𝛼𝐴𝛽 → 𝛿