List of Important Abbreviations – Formal Languages and Automata Theory

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

Non-deterministic Finite Automata

DFA

Deterministic Finite Automata

FSM

Finite State Machine

LMD

Left-most Derivation

RMD

Right-most Derivation

ID

Instantaneous Description

CNF

Chomsky Normal Form

GNF

Greibach Normal Form

RHS

Right-hand Side

LHS

Left-hand Side

CYK

Cocke–Younger–Kasami

PDA

Pushdown Automata

LBA

Linear-bound Automata

TM

Turing Machine

LIFO

Last-in-first-out

NPDA

Non-deterministic Pushdown Automata

DPDA

Deterministic Pushdown Automata

YACC

Yet another Compiler Compiler

DCFL

Deterministic Context-Free Language

DCFG

Deterministic Context-Free Grammar

NTM

Non-deterministic Turing Machine

PCP

Post-Correspondence Problem

MPCP

Modified Post-Correspondence Problem

NP

Non-deterministic Polynomial time

NPC

NP-Complete

TSP

Travelling Salesman Problem

LR(K)

Left-to-right scan of input, producing a right-most derivation using K symbols look ahead

LL(1)

Left-to-right scan of input, using Left-most derivation with 1 symbol look ahead

w.f.f.

well formed formulae

RE

Regular Expression

GNFA

Generalized NFA