Operações Fechadas
sobre linguagens regulares
O que são operações fechadas sobre linguagens regulares?
Definição: Existem muitas operações que, quando aplicadas a LR resultam em uma LR (dizemos que são fechadas). Entre elas temos: união, complemento e intersecção (operações booleanas), concatenação, fechamento e diferença
Em outras palavras:
São operações utilizadas para construir linguagens mais complexas a partir de outras linguagens mais simples. As operações usadas são: união, concatenação, complemento, diferença, intersecção e fecho.
Assim, quando temos duas uma linguagens simples podemos criar uma outra mais complexa gerando um autômato finito que tem como conjunto o resultado das outras duas mais simples.
Quando/Onde/Por que são usadas essas operações?
As operações fechada são utilizadas para:
- Construir linguagens mais complexas através do uso dessas operações aplicadas em linguagens mais simples.
- Provar propriedades
- Construir algoritmos
Lembrando que:
- As linguagens regulares são representadas por autômatos finitos que podem ser determinísticos ou não determinísticos com memória limitada
- Autômato Finito (AF)
Definição: é um modelo de máquina definido formalmente por uma quíntupla M = (Σ , Q, δ, q0, F), onde:
Σ : alfabeto de símbolos de entrada
Q: conjunto finito de estados possíveis para M
δ: função transição ou função programa
q0: estado inicial de M, sendo q0 ∈Q
F: conjunto de estados finais, tal que F⊆ Q