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
(um conjunto finito de símbolos) e notemos que
é o conjunto de todas as cadeias (strings) formadas por símbolos de
. Uma linguagem
sobre
é qualquer subconjunto
. Agora dizemos que
é uma linguagem regular se existe um autômato finito determinístico
tal que
é exatamente o conjunto de cadeias aceitas por
. Em detalhe:
– é um conjunto finito de estados.
– é a função de transição.
– é o estado inicial.
– é o conjunto de estados finais.
Uma cadeia pertence a
se, ao processar
desde
seguindo
, o autômato termina em um estado de
.
–
–
–
–
Uma cadeia
Passo 3
Além da caracterização por autômatos finitos, podemos dizer que uma linguagem
sobre
é 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
com
símbolos não-terminais e
). 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
é dita regular se e somente se satisfaz qualquer (e, portanto, todas) das condições a seguir:
- Existe um autômato finito determinístico
tal que . - Existe uma expressão regular que gera exatamente
. - Existe uma gramática tipo-3 (regular) que gera
.