Formal Languages

Alphabet

• An alphabet is a nonempty finite set $\Sigma$ of symbols (or letters).
  • Symbols are typically denoted by $\text{a},\text{b},\text{c},\dots$.

Strings

• A string over an alphabet $\Sigma$ is a finite sequence of symbols from $\Sigma$, usually written without separators.
  • Strings are typically denoted by lowercase letters $w,x,y,z,...$.
• The length of a string $w$, written $|w|$, is the number of symbols in $w$.
• The set of all possible strings over an alphabet $\Sigma$ is denoted by ${\Sigma }^{\ast }$.
• The string of length zero is called the empty string, denoted by $\epsilon \in {\Sigma }^{\ast }$.
  • The empty string is a substring of every string.
  • $\epsilon w=w\epsilon =w$
  • $|\epsilon |=0$
• A prefix of a string $w$ is a string $u$ such that $w=uz$ for some string $z$.
• A suffix of a string $w$ is a string $v$ such that $w=zv$ for some string $z$.
• A substring of a string $w$ is a string $t$ such that $w=put$ for some strings $p,s\in {\Sigma }^{\ast }$.
• A proper prefix/suffix/substring is a prefix/suffix/substring that is not equal to $w$.
• The lexicographic order of strings follows dictionary order.
• The shortlex order (or string order) is a lexicographic order where shorter strings precede longer ones.

Operations

• For strings $x,y\in {\Sigma }^{\ast }$, their concatenation is written as $xy$ or $x\cdot y$ and is the string formed by appending $y$ to $x$.
• The reverse of a string $w$, written $w^{\mathcal{R}}$, is the string obtained by writing $w$ in the opposite order.
• A power of a string $x$, written $x^k$, represents $x$ concatenated with itself $k$ times.

Grammar

• A formal grammar is a tuple $G=(V,\Sigma ,R,S)$ where
  • $V$ is a finite set of variables (or non-terminals)
    • Symbolized by $A,B,\dots$
    • (In other areas, these are called syntactic categories)
  • $\Sigma$ is a finite set of terminals (with $V$ and $\Sigma$ disjoint)
    • Symbolized by $a,b,\dots$
    • This is the alphabet of the language
  • $R$ is a finite set of rules (or productions)
    • A rule is a string of the form $(\Sigma \cup N{)}^{\ast }N(\Sigma \cup N{)}^{\ast }\to (\Sigma \cup N{)}^{\ast }$
    • A $\epsilon$-rule is a rule of the form $A\to \epsilon$, where $A\in V$.
    • An unit rule is a rule of the form $A\to B$, where $A,B\in V$.
    • A variable $A$ is nullable if $A\stackrel{\ast }{\Rightarrow }\epsilon$.
  • $S\in V$ is the start variable

Languages

• Any subset $L\subseteq {\Sigma }^{\ast }$ is called a language over $\Sigma$.

  • A language is prefix-free if no string in it is a proper prefix of another.

• The strings in a language are called words.

• The empty set $\varnothing$ is a language, called the empty language.

  • $L\cdot \varnothing =\varnothing \cdot L=\varnothing$
  • ${\varnothing }^{\ast }=\{\epsilon \}$
  • $\varnothing$ is regular
  • ${\varnothing }^{+}=\varnothing$

• The set $\{\epsilon \}$ is a language (sometimes called the empty string language)

  • $\{\epsilon \}={\varnothing }^{\ast }$
  • $\{\epsilon \}$ is regular
  • $\{\epsilon {\}}^{\ast }=\{\epsilon \}$

• $L^{\ast }=\bigcup _{i=0}^{\infty }{L}^i$

• $L^0=\{\epsilon \}$

• $L\cdot \{\epsilon \}=\{\epsilon \}\cdot L=L$

Operations & Closure Properties

Operation		Regular	CFL	Decidable (R)	Turing-recognizable (RE)
Union	$L_1\cup L_2=\{w\mid w\in L_1\vee w\in L_2\}$	Yes	Yes	Yes	Yes
Intersection	$L_1\cap L_2=\{w\mid w\in L_1\wedge w\in L_2\}$	Yes	╳	Yes	Yes
Complement	$\overline{L_1}=\{w\mid w\notin L_1\}$	Yes	╳	Yes	╳
Concatenation	$L_1\cdot L_2=\{wz\mid w\in L_1\wedge z\in L_2\}$	Yes	Yes	Yes	Yes
Kleene Star	$L_1^{\ast }=\{\epsilon \}\cup \{wz\mid w\in L_1\wedge z\in L_1^{\ast }\}$	Yes	Yes	Yes	Yes
Reverse	$L^{\mathcal{R}}=\{w^{\mathcal{R}}\mid w\in L\}$	Yes	Yes	Yes	Yes
Homomorphism		Yes	Yes	╳	Yes
Intersection with a regular lang. $R$	$L\cap R=\{w\mid w\in L\wedge w\in R\}$	Yes	Yes	Yes	Yes

Classification

Chomsky Hierarchy	Language/Grammar	Abstract Machine
Type-0	Turing-recognizable (RE) / Unrestricted	Turing Machine
Type-1	Context-Sensitive	Linear Bounded Automaton
Type-2	Context-Free	Pushdown Automaton
Type-3	Regular	Finite State Automaton

Automata

Automaton
Deterministic Finite Automaton (DFA)
Nondeterministic Finite Automaton (NFA)
$\cap$
Deterministic Push Down Automaton (DPDA-I) with 1 push-down store
$\cap$
Nondeterministic Push Down Automaton (NPDA-I, PDA) with 1 push-down store.
$\cap$
Linear Bounded Automaton (LBA)
$\cap$
Deterministic Push Down Automaton (DPDA-II) with 2 push-down stores
Nondeterministic Push Down Automaton (NPDA-II) with 2 push-down stores
Deterministic Turing Machine (DTM)
Nondeterministic Turing Machine (NTM)
Probabilistic Turing Machine (PTM)
Multitape Turing Machine (MTM)
Multidimensional Turing Machine