List of Important Abbreviations
URG 
Unrestricted Grammar 
CSG 
Context Sensitive Grammar 
CFG 
Context Free Grammar 
RG 
Regular Grammar 
RL 
Regular Language 
CFL 
Context Free Language 
CSL 
Context Sensitive Language 
REL 
Recursively Enumerable Language 
CPU 
Central Processing Unit 
FA 
Finite Automata 
NFA 
Nondeterministic Finite Automata 
DFA 
Deterministic Finite Automata 
FSM 
Finite State Machine 
LMD 
Leftmost Derivation 
RMD 
Rightmost Derivation 
ID 
Instantaneous Description 
CNF 
Chomsky Normal Form 
GNF 
Greibach Normal Form 
RHS 
Righthand Side 
LHS 
Lefthand Side 
CYK 
Cocke–Younger–Kasami 
PDA 
Pushdown Automata 
LBA 
Linearbound Automata 
TM 
Turing Machine 
LIFO 
Lastinfirstout 
NPDA 
Nondeterministic Pushdown Automata 
DPDA 
Deterministic Pushdown Automata 
YACC 
Yet another Compiler Compiler 
Deterministic ContextFree Language 

DCFG 
Deterministic ContextFree Grammar 
NTM 
Nondeterministic Turing Machine 
PCP 
PostCorrespondence Problem 
MPCP 
Modified PostCorrespondence Problem 
NP 
Nondeterministic Polynomial time 
NPC 
NPComplete 
TSP 
Travelling Salesman Problem 
LR(K) 
Lefttoright scan of input, producing a rightmost derivation using K symbols look ahead 
LL(1) 
Lefttoright scan of input, using Leftmost derivation with 1 symbol look ahead 
w.f.f. 
well formed formulae 
RE 
Regular Expression 
GNFA 
Generalized NFA 