Showing posts with label FINITE STATE AUTOMATA. Show all posts
Showing posts with label FINITE STATE AUTOMATA. Show all posts

Tuesday, June 02, 2020

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


Search Aptipedia