Uma expressão regular sobre um alfabeto  é uma cadeia sobre   {), (, , , *}, tal que:
a) , assim como cada símbolo de  é uma expressão regular;
b) Se  e  são expressões regulares, () também é;
c) Se  e  são expressões regulares, (  ) também é;
d) Se  é expressão regular então * também é;
e) Nada será expressão regular se não seguir as regras de a) até d).

S – Símbolo inicial (a partir do qual derivam-se as cadeias da linguagem);
Derivação
Processo através do qual as cadeias de uma linguagem são geradas. Representa-se através do símbolo , que representa uma substituição em uma forma sentencial
(usando alguma regra ). A linguagem gerada por G é representada por L(G), e, tem-se:
L(G) = {w | S * w …exibir mais conteúdo…

Uma configuração é um elemento do conjunto K  *. Como é possível acompanhar a evolução do processo a cada momento, define-se sobre o conjunto das configurações a relação M , que indica um par de configurações sucessivas durante o processo computacional, isto é, indica um passo computacional
(um único movimento do modelo de autômato sobre o conjunto de configurações). O fecho transitivo e reflexivo da relação de passo é denotado por M*.
Usando a definição anterior pode-se definir a linguagem aceita por um autômato finito M=(K, , , s, F) como:
L(M) = {w  * | (s, w) M* (q, ), q  F}, isto é, todas as cadeias que M aceite.

A representação pode ser feita através de um grafo orientado com as indicações dos estados finais e do estado inicial, como também pode ser através da descrição dos componentes da quíntupla, com uma tabela representando a função .

Minimização de autômatos finitos determinísticos
Processo pelo qual se busca encontrar um outro modelo de autômato finito determinístico que aceite a mesma linguagem, e cujo conjunto de estados tenha tamanho mínimo. Autômato Finito Não-Determinístico
Indica a possibilidade de mudar de estado de uma forma que é apenas parcialmente determinada através do estado corrente e do símbolo capturado na fita de entrada. Isto indica que pode haver várias possibilidades para o