Sejam $A$ e $B$ dois conjuntos quaisquer, uma função $f$ de $A$ em $B$, denotado como $f:A\to B$, é uma relação que associa cada elemento de $A$ a, no máximo, um elemento em $B$.

Sejam $A$ e $B$ dois conjuntos quaisquer, e sejam $f$ e $g$ funções de $A$ em $B$, isto é, $f,g:A\to B$. Dizemos que $f$ é uma função parcial quando não está definida para todos os elementos de $A$. Por outro lado, $f$ é uma função total quando está definida para todos os elementos de $A$.

Um alfabeto é um conjunto de símbolos finito e não vazio denotado convencionalmente pelo símbolo $\Sigma$.

Seja $\Sigma$ um alfabeto, qualquer sequência finita de símbolos na forma $a_1\cdots a_n$ com $a_i\in \Sigma$ para todo $1\le i\le n$ é dita uma palavra sobre $\Sigma$.

Seja $w$ uma palavra, o comprimento de $w$, denotado por $\left|w\right|$, é o número de símbolos que compõem $w$.

Seja $w$ uma palavra, $w$ é dita palavra vazia, e denotada por $\lambda$, se, e somente se, $\left|w\right|=0$.

Sejam $w_1=a_1\cdots a_n$ e $w_2=b_1\cdots b_m$ duas palavas quaisquer, a concatenação de $w_1$ com $w_2$, denotada por $w_1{w}_2$ é a palavra formada por todos os símbolos de $w_1$ seguidos por todos os símbolos de $w_2$, ou seja: $$w_1{w}_2=a_1\cdots a_n{b}_1\cdots b_m$$

Seja uma palavra $w$, a palavra potência de $w$, denotada por $w^n$, é definida recursivamente como: $$w^0=\lambda$$ $$w^{n+1}=w{w}^n$$

Seja uma palavra $w=a_1\cdots a_n$, a palavra inversa de $w$, denotada por $w^r$, é tal que $w^r=a_n\cdots a_1$.

Seja um alfabeto $\Sigma$, a potência de $\Sigma$, denotada por ${\Sigma }^n$, é definida recursivamente como: $${\Sigma }^0=\{\lambda \}$$ $${\Sigma }^{n+1}=\{aw\mid a\in \Sigma ,w\in {\Sigma }^n\}$$

Seja $\Sigma$ um alfabeto, o fecho positivo e o fecho de Kleene de $\Sigma$, denotados em ordem por ${\Sigma }^{+}$ e ${\Sigma }^{\ast }$, correspondem, respectivamente, aos conjuntos: $${\Sigma }^{+}=\bigcup _{i=1}^{\infty }{\Sigma }^i\text{ e }{\Sigma }^{\ast }=\bigcup _{i=0}^{\infty }{\Sigma }^i$$

Seja as palavra $w,u,v\in {\Sigma }^{\ast }$, dizemos que $u$ é prefixo de $w$, denotado por $u{\preccurlyeq }_{p}w$, sempre que $w=uv$. Por outro lado, dizemos que $u$ é sufixo de $w$, denotado por $u{\preccurlyeq }_{s}w$, sempre que $w=vu$.

Seja $w\in {\Sigma }^{\ast }$, o conjunto de todos os prefixos de $w$ corresponde ao conjunto: $$PRE\left(w\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_{p}w\}$$ e o conjunto de todos os sufixo de $w$ corresponde ao conjunto $$SUF\left(w\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_{s}w\}$$

Dado um alfabeto $\Sigma$, qualquer subconjunto $L\subseteq {\Sigma }^{\ast }$ será chamado de linguagem sobre $\Sigma$.

Sejam as linguagens $L_1,L_2$, a concatenação de $L_1$ e $L_2$, denotado por $L_1{L}_2$, corresponde ao conjunto: $$L_1{L}_2=\{uv\in {\left({\Sigma }_1\cup {\Sigma }_2\right)}^{\ast }\mid u\in L_1,v\in L_2\}$$

Seja $L$ uma linguagem, a linguage m reversa de L, denotada por $L^r$, corresponde ao conjunto: $$L^r=\{w^r\mid w\in L\}$$

Seja uma linguagem $L$, a linguagem potência de $L$, denotada por $L^n$, é definida recursivamente como:
$$L^0=\{\lambda \}$$ $$L^n=L{L}^{n-1}$$

Seja $L$ uma linguagem, o Fecho Positivo e o Fecho de Kleene de L, denotados em ordem por $L^{+}$ e $L^{\ast }$, são, respecivamente: $$L^{+}=\bigcup _{i=1}^{\infty }{L}^i\text{ e }{L}^{\ast }=\bigcup _{i=0}^{\infty }{L}^i$$

Seja $L$ uma linguagem, as linguagens dos prefixos e dos sufixos de $L$, denotadas em ordem por $PRE\left(L\right)$ e $SUF\left(L\right)$, são, respectivamente, os seguintes conjuntos: $$PRE\left(L\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_p,w\in L\}$$ $$SUF\left(L\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_s,w\in L\}$$

Um Autômato Finito Determinístico (AFD) é uma quintupla $$A=⟨\mathcal{Q},\Sigma ,\delta ,q_0,F⟩$$ onde:

• $\mathcal{Q}$ é um conjunto não-vazio e finito de estados internos.
• $\Sigma$ é um alfabeto de entrada.
• $\delta :\mathcal{Q}\times \Sigma \to \mathcal{Q}$ é uma função total de transição.
• $q_0\in \mathcal{Q}$ é o estado inicial.
• $F\subseteq \mathcal{Q}$ é o conjunto de estados finais ou de aceitação.

Seja um AFD $A=⟨\mathcal{Q},\Sigma ,\delta ,q_0,F⟩$, a função estentida de $\delta$, denotada por $\hat{\delta }$, é $\hat{\delta }:\mathcal{Q}\times {\Sigma }^{\ast }\to \mathcal{Q}$, tal que: $$\hat{\delta }\left(q,\lambda \right)=q$$ $$\hat{\delta }\left(q,wa\right)=\delta \left(\hat{\delta }\left(q,w\right),a\right)$$

Seja $A$ um AFD e seja $w\in {\Sigma }^{\ast }$, uma computação de $w$ em $A$ corresponde a aplicação de $\hat{\delta }\left(q_0,w\right)$.

Seja $A$ um AFD e seja $w\in {\Sigma }^{\ast }$ é dito que $w$ é reconhecida por $A$ sempre que $\hat{\delta }\left(q_0,w\right)\in F$.

Seja $A$ um AFD, a linguagem reconhecida (computada) $A$, denotada por $\mathcal{L}\left(A\right)$, corresponde ao conjunto: $$\mathcal{L}\left(A\right)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }\left(q_0,w\right)\in F\}$$

Seja $L$ uma linguagem qualquer, $L$ é dita linguagem regular se, e somente se, existe um AFD $A$ tal que $L=\mathcal{L}\left(A\right)$. A classe de todas as linguagens regulares é denotada por ${\mathcal{L}}_{Reg}$.

Um Autômato Finito Não-determinístico (AFN) é uma quintupla $$A=⟨\mathcal{Q},\Sigma ,{\delta }_N,q_0,F⟩$$ onde:

• $\mathcal{Q}$ é um conjunto não-vazio e finito de estados internos.
• $\Sigma$ é um alfabeto de entrada.
• ${\delta }_N:\mathcal{Q}\times \Sigma \to \wp \left(\mathcal{Q}\right)$ é uma função total de transição.
• $q_0\in \mathcal{Q}$ é o estado inicial.
• $F\subseteq \mathcal{Q}$ é o conjunto de estados finais ou de aceitação.

Seja $A=⟨\mathcal{Q},\Sigma ,{\delta }_N,q_0,F⟩$ um AFN. Define-se a função de transição não-determinística estendida $${\hat{\delta }}_N:\mathcal{Q}\times {\Sigma }^{\ast }\to \wp \left(Q\right),$$ tal que: $${\hat{\delta }}_N\left(q,\lambda \right)=q$$ $${\hat{\delta }}_N\left(q,wa\right)=\bigcup _{q^{\prime }\in {\hat{\delta }}_N\left(q,w\right)}{\delta }_N\left(q^{\prime },a\right),$$ para todo $q\in \mathcal{Q}$, $w\in {\Sigma }_{\ast }$ e $a\in \Sigma$.

Um $\lambda$-Autômato Finito Não-determinístico ($\lambda$-AFN) é uma estrutura $$A=⟨\mathcal{Q},\Sigma ,\underline{{\delta }_N},q_0,F⟩,$$ onde:

• $\mathcal{Q}$ é um conjunto não-vazio e finito de estados internos.
• $\Sigma$ é um alfabeto de entrada.
• $\underline{{\delta }_N}:\mathcal{Q}\times \left(\Sigma \cup \{\lambda \}\right)\to \wp \left(\mathcal{Q}\right)$ é uma função total de transição.
• $q_0\in \mathcal{Q}$ é o estado inicial.
• $F\subseteq \mathcal{Q}$ é o conjunto de estados finais ou de aceitação.

Seja $A=⟨\mathcal{Q},\Sigma ,\underline{{\delta }_N},q_0,F⟩$ um $\lambda$-AFN. A função $${\delta }_{\lambda }:\mathcal{Q}\to \wp \left(\mathcal{Q}\right)$$ é definida como $${\delta }_{\lambda }\left(q\right)=\bigcup _{i=0}^n\lambda {\text{-fecho}}^i\left(q\right),$$ onde $n=\#\mathcal{Q}-1$ e $$\begin{array}{rl}\lambda {\text{-fecho}}^0\left(q\right)& =\{q\}\\ \lambda {\text{-fecho}}^i\left(q\right)& =\bigcup _{q^{\prime }\in \lambda {\text{-fecho}}^{i-1}\left(q\right)}\underline{{\delta }_N}\left(q^{\prime },\lambda \right).\end{array}$$

Seja $A=⟨\mathcal{Q},\Sigma ,\underline{{\delta }_N},q_0,F⟩$ um $\lambda$-AFN. A função $${\hat{\delta }}_{\lambda }:\wp \left(\mathcal{Q}\right)\to \wp \left(\mathcal{Q}\right)$$ é definida como $${\hat{\delta }}_{\lambda }\left(X\right)=\bigcup _{q\in X}{\delta }_{\lambda }\left(q\right).$$

Seja $A=⟨\mathcal{Q},\Sigma ,\underline{{\delta }_N},q_0,F⟩$ um $\lambda$-AFN. A $\lambda$-Função de Transição Não-determinística Estendida $$\underline{{\hat{\delta }}_N}:\mathcal{Q}\times {\Sigma }^{\ast }\to \wp \left(\mathcal{Q}\right),$$ é definida recursivamente como: $$\begin{array}{rl}\underline{{\hat{\delta }}_N}\left(q,\lambda \right)& ={\delta }_{\lambda }\left(q\right)\\ \underline{{\hat{\delta }}_N}\left(q,wa\right)& =\bigcup _{q^{\prime }\in \underline{{\hat{\delta }}_N}\left(q,w\right)}{\hat{\delta }}_{\lambda }\left(\underline{{\delta }_N}\left(q^{\prime },a\right)\right).\end{array}$$