Subject: Compilers
Links: Strings and Grammars

Assume that two expressions $e_1$ and $e_2$ generate the languages $L_1$ and $L_2$, respectively. Concatenation, is then defined as $e_1{e}_2:=\{xy\mid x\in L_1,y\in L_2\}$. Alternation, which is denoted as $|$ is the union of the two languages, $e_1|e_2:=\{x\in L_1\vee x\in L_2\}$. Closure, which is represented by braces $\{\}$, denotes the repetition of the expression $n$ times for $n<\omega$, $\{e_1\}:=\{x\in L_1^{\ast }\}$.

Def: Regular expressions are those expression that can be constructed from the following rules:

• $\varphi$ is regular expression denoting the $\varnothing$.
• $\epsilon$ is regular expression denoting the language consisting of only the empty string, $\{\epsilon \}$.
• $a$, where $a\in V_T$, is a regular expression denoting the language of the single symbol $a$, that is, $\{a\}$.
• If $e_1$ and $e_2$ are regular expressions denoting the languages $L_1$ and $L_2$, respectively, then:
  • $(e_1)|(e_2)$ is a regular expression denoting $L_1\cup L_2$.
  • $(e_1)(e_2)$ is a regular expression denoting $L_1{L}_2$.
  • $\{e_1\}$ is a regular expression denoting $L_1^{\ast }$.

Def: Two regular expression are equal $(=)$ or equivalentif they denote the same language.

Finite-State Automatons

Def: A deterministic finite-state automaton is a $5$-tuple $(K,V_T,M,S,Z)$ where:

• $K$ is a finite nonempty set of elements called states
• $V_T$ is an alphabet called the input alphabet.
• $M$ is a mapping from $K\times V_T$ to $K$.
• $S\in K$ is called the initial state of starting state.
• $Z\subseteq K$ is a nonempty set of final states.
  The mapping $M$ must follow the following conditions:
• $M(Q,\epsilon )=Q$ for every $Q\in K$.
• $M(Q,Tt)=M(M(Q,T),t)$ fro all $T\in V_T$ and $t\in V_T^{\ast }$.

A sentence $t$ is said to be accepted by a DFA if $M(S,t)=P$ for some DFA $F=(K,V_T,M,S,Z)$ such that $t\in V_T^{\ast }$ and $P\in Z$. Thus we define $$L(F) := {t \mid M(S, t) \in Z \land t\in V_T^*}.$$

Nondeterministic Finite-State Automatons

Def: A nondeterministic finite-state automaton is $5$-tuple $(K,V_T,M,S,Z)$ where:

• $K$ is a finite nonempty set of elements called states
• $V_T$ is an alphabet called the input alphabet.
• $M$ is a mapping from $K\times V_T$ to $2^K$.
• $S\in K$ is called the initial state of starting state.
• $Z\subseteq K$ is a nonempty set of final states.
  The mapping $M$ now must satisfy the following:$$
  \begin{align*}
  M(Q, \varepsilon) = {Q} \qquad \qquad \qquad &\text{where $Q\in K$}\
  M(Q, Tt) = \bigcup_{P \in M(Q, T)} M(P, t) \qquad &\text{where $T\in V_T$ and $t\in V_T^{\ast }$} \
  M({Q_1, \dots Q_n}, x) = \bigcup_{i = 1}^n M(Q_i, x) \qquad & \text{where $x\in V_T^{\ast }$}
  \end{align*}$$We also extend the definition of a NFA to accept an string $x\in V_T^{\ast }$ so that $M(S,x)\cap Z\ne \varnothing$.

Th: Let $F=(K,V_T,M.S,Z)$ be a nondeterministic finite-state automaton accepting a set of strings $L$. Define a DFA $F^{\prime }=(K^{\prime },V_T,M^{\prime },S^{\prime },Z^{\prime })$ as follows:

• The alphabet of states consiste of all the subsets of $K$. An element of $K^{\prime }$ is denoted as $[S_1,\dots ,S_i]$ where $S_1,\dots S_i$ are states fo $K$. The states $S_1,\dots ,S_i$ are in the same canonical order so that form some states in $K$, $\{S_1,S_2\}=\{S_2,S_1\}$ is always $[S_1,S_2]$.
• The set of input characters $V_T$ is the same for $F$ and $F^{\prime }$.
• The mapping $M^{\prime }$ is defined as $$M'([S_1, \dots, S_i], T) = [R_1, \dots R_j]$$where $$M({S_1, \dots, S_i}, T) = {R_1, \dots R_j}.$$
• If the starting state of $S$, then $S^{\prime }=[S]$.
• $Z^{\prime }$ us the set of all states in $K^{\prime }$ containing a final stat in $Z$.
  Then the set of string accepted by $F^{\prime }$ is the same as for $F$.

Def: A nondeterministic finite-state automaton with $\epsilon$-transitions is a $5$-tuple $(K,V_T,M.S,Z)$, where $K$, $V_T$, $S$ and $Z$ are the same as for a NFA and $M$ is a mapping $K\times (V_T\cup \{\epsilon \})$ into $2^K$.

Def: $\epsilon$-Closure is a set of states of a NFA with $\epsilon$-transitions, say $F$ such that $\epsilon$-closure for some state of $F$, call it $q$, includes all attainable states from the state by making state transition with $\epsilon$-transitions. This is denoted by $\epsilon -\text{Closure}(q)$.

Th: Define $F=(K,V_T,M.S,Z)$ as a NFA with $\epsilon$-transitions. Then there exists an NFA $F^{\prime }$ without $\epsilon$-transitions such that $L(F)=L(F^{\prime })$.

Th: There exists a nondeterministic finite-state auntomaton $F=(K,V_T,M.S,Z)$ which accepts the language generated by the regular grammar $G=(V_N,V_T,S,\mathrm{\Phi })$.

Th: There exists a regular grammar $G=(V_N,V_T,S,\mathrm{\Phi })$ which produces the language accepted by a given deterministic finite-state automaton $F=(K,V_T,M.S,Z)$.