CHOMSKY HIERARCHY FOR FORMAL LANGUAGES IN THEORY OF COMPUTATION

SN

FORMAL LANGUAGE

LANGUAGE EXAMPLE

FORMAL GRAMMAR

GRAMMAR DEFINITION

TYPE

AUTOMATA /MACHINE

TYPE OF AUTO MATA/MACHINE

MACHINE DEFINITION

#TUPLE

#PARAMETER  IN δ

#COMPONENT IN MACHINE

MACHINE COMPONENT

1

REGULAR LANGUAGE (RL)

L={an|n>=1}

REGULAR GRAMMAR (RG)

S->aS S->a S->ε

TYPE - 3

FINITE STATE AUTOMATA (FSA)

1. DETERMINISTIC FSA 2. NON- DETERMINISTIC FSA

Q - SET OF STATES Σ - SET OF INPUTS q0 - INITIAL STATE F - FINAL STATE (S) δ - TRANSITION FUNCTION

5

2/1

3

1. INPUT TAPE 2. READ HEAD 3. FINITE CONTROL

2

CONTEXT FREE LANGUAGE (CFL)

L={anbn|n>=1}

CONTEXT FREE GRAMMAR (CFG)

S->aSb S->ε

TYPE - 2

PUSH DOWN AUTOMATA (PDA)

1. DETERMINISTIC PDA 2. NON- DETERMINISTIC PDA

Q - SET OF STATES Σ - SET OF INPUTS Γ - STACK SYMBOL q0 - INITIAL STATE F - FINAL STATE (S) δ - TRANSITION FUNCTION

6

2/3

5

1. INPUT TAPE 2. READ HEAD 3. FINITE CONTROL 4. STACK 5. STACK TOP

3

CONTEXT SENSITIVE LANGUAGE (CSL)

L={anbncn|n>=1}

CONTEXT SENSITIVE GRAMMAR (CSG)

S->aSb Sa->ABC aS->AbC BS->abc |α|<=|β|

TYPE - 1

LINEAR BOUNDED AUTOMATA (LBA)

1. DETERMINISTIC LBA 2. NON- DETERMINISTIC LBA

Q - SET OF STATES Σ - SET OF INPUTS Γ - STACK SYMBOL q0 - INITIAL STATE F - FINAL STATE (S) # - BLANK SPACE < - LEFT END MARKER > - RIGHT END MARKER δ - TRANSITION FUNCTION

9

2/3

5

1. INPUT TAPE 2. READ HEAD 3. FINITE CONTROL 4. R/W HEAD 5. WORKING TAPE

4

RECURSIVE ENUMERABLE LANGUAGE (REL)

RECURSIVE ENUMERABLE GRAMMAR (REG)

S-> ACaB CaBc->aaC aD->DB AE->ε

TYPE - 0

TURING MACHINE

1. DETERMINISTIC TM 2. NON- DETERMINISTIC TM 3. SINGLE TAPE TM 4. MULTITAPE TM 5. TWO WAY INFINITE TM 6. UNIVERSAL TM

Q - SET OF STATES Σ - SET OF INPUTS Γ - STACK SYMBOL q0 - INITIAL STATE h - HALTING STATE # - BLANK SPACE δ - TRANSITION FUNCTION

7

2/3

3

1. INPUT TAPE 2. R/W HEAD 3. FINITE CONTROL