Defina Linguagem Regular.

Passo 1

O enunciado pede para definirmos o que é uma linguagem regular. O tema está em Teoria de Autômatos e Linguagens Formais. Para resolver, vamos lembrar o que são alfabetos, cadeias e linguagens, e em seguida apresentar a definição de linguagem regular usando autômatos finitos e realçar as outras caracterizações equivalentes (expressões regulares e gramáticas lineares à direita).

Passo 2

Primeiro, fixemos um alfabeto \Sigma (um conjunto finito de símbolos) e notemos que \Sigma^* é o conjunto de todas as cadeias (strings) formadas por símbolos de \Sigma. Uma linguagem L sobre \Sigma é qualquer subconjunto L \subseteq \Sigma^*. Agora dizemos que L é uma linguagem regular se existe um autômato finito determinístico
M = (Q, \Sigma, \delta, q_0, F)
tal que L é exatamente o conjunto de cadeias aceitas por M. Em detalhe:
Q é um conjunto finito de estados.
\delta \colon Q \times \Sigma \to Q é a função de transição.
q_0 \in Q é o estado inicial.
F \subseteq Q é o conjunto de estados finais.
Uma cadeia w \in \Sigma^* pertence a L se, ao processar w desde q_0 seguindo \delta, o autômato termina em um estado de F.

Passo 3

Além da caracterização por autômatos finitos, podemos dizer que uma linguagem L sobre \Sigma é regular se e somente se ela pode ser descrita por uma expressão regular ou gerada por uma gramática livre de contexto especial chamada gramática regular (mais precisamente, gramática tipo-3, onde cada produção tem a forma
A \to aB \quad\text{ou}\quad A \to a
com A,B símbolos não-terminais e a\in\Sigma). Essas três visões (autômatos finitos, expressões regulares e gramáticas tipo-3) são todas equivalentes entre si.

Resposta

Uma linguagem L\subseteq\Sigma^* é dita regular se e somente se satisfaz qualquer (e, portanto, todas) das condições a seguir:
  1. Existe um autômato finito determinístico M tal que L = L(M).
  2. Existe uma expressão regular que gera exatamente L.
  3. Existe uma gramática tipo-3 (regular) que gera L.

Exercícios relacionados