Scribd
Upload
6 views1 page

C445 Lecture24

The document outlines the Chomsky Hierarchy, categorizing grammars, languages, and their corresponding accepting machines into four types: Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). It details the relationships between these families, indicating that each type of grammar and language is a subset of the next, with increasing restrictions. Additionally, it describes how different abstract machines relate to the languages they can accept, showing a hierarchy from finite state automata to Turing machines.

Uploaded by

zvyrgefqxckkugfgay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

C445 Lecture24

The document outlines the Chomsky Hierarchy, categorizing grammars, languages, and their corresponding accepting machines into four types: Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular). It details the relationships between these families, indicating that each type of grammar and language is a subset of the next, with increasing restrictions. Additionally, it describes how different abstract machines relate to the languages they can accept, showing a hierarchy from finite state automata to Turing machines.

Uploaded by

zvyrgefqxckkugfgay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Dr.

Hasmik Gharibyan
Chomsky Hierarchy

Grammars Languages Accepting Machines

Type 0 grammars:
Unrestricted Recursively enumerable Turing Machine

Type 1 grammars:
Context-sensitive Context-sensitive Linear-bounded automaton

Type 2 grammars:
Context-free Context-free Push-down automaton

Type 3 grammars:
Regular Regular Finite State automaton

Note: The restrictions placed on the rules increase with the number of the grammar.

Relationships between the families of grammars:


Every regular grammar is context-free
Every context-free grammar that doesn’t contain a λ-rule is context-sensitive
Every context-free grammar is unrestricted
Every context-sensitive grammar is unrestricted

Relationships between the families of languages:


Every regular language is context-free
Every context-free language that doesn’t contain the λ-string is context-sensitive
Every context-free language is recursively enumerable
Every context-sensitive language is recursively enumerable

Relationships between the families of abstract machines:


PDAs can accept any language that Finite Automata accept
Linear Bounded Automata can accept any language that PDAs accept
Turing Machines can accept any language that Linear Bounded Automata accept

You might also like