Família abstrata de linguagens

Na ciência da computação, em particular no campo da teoria das linguagens formais, o termo família abstrata de linguagens se refere a uma noção matemática abstrata que generaliza característas comuns a linguagens regulares, linguagens livres de contexto e a linguagens recursivamente enumeráveis, e outras famílias de linguagens formais estudadas na literatura científica.

Definições formais

Uma linguagem formal é um conjunto $L$ para o qual existe um conjunto finito de símbolos abstratos $\mathrm{\Sigma }$ tais que $L\subseteq {\mathrm{\Sigma }}^{*}$, onde * é a operação do Fecho de Kleene.

Uma família de linguagens é um par ordenado $(\mathrm{\Sigma },\mathrm{\Lambda })$, onde

1. $\mathrm{\Sigma }$ é um conjunto infinito de símbolos;
2. $\mathrm{\Lambda }$ é um conjunto de linguagens formais;
3. Para cada $L$ em $\mathrm{\Lambda }$ existe um subconjunto finito ${\mathrm{\Sigma }}_1$ ⊂ $\mathrm{\Sigma }$ tal que $L$ ⊆ ${\mathrm{\Sigma }}_1^{*}$; e
4. $L$ ≠ Ø para algum $L$ em $\mathrm{\Lambda }$.

Um trio é um família de linguagens fechadas sob homomorfismo, homomorfismo inverso, e interseção com linguagem regular.

Um trio completo, também chamado de cone, é um trio fechado sob homomorfismo arbitrário.

Um semi-FLA(completo) é um trio(completo) fechado sob união.

Um FLA(completo) é um semi-FLA(completo) fechado sob concatenação e fecho de Kleene.

Algumas famílias de linguagens

A seguir estão alguns resultados simples dos estudos das famílias abstratas de linguagens.

Dentro da hierarquia de Chomsky, as linguagens regulares, as linguagens livre de contexto, e as linguagens recursivamente enumeráveis são FLAs completas. Contudo, as linguagens sensíveis ao contexto e as linguagens recursivas são FLAs, mas não FLAs-completas porque não são fechadas sob homomorfismos arbitrários.

A família de linguagens regulares estão contidas dentro de qualquer cone (trio completo). Outras categorias de famílias abstratas são identificadas pelo fechamento sob operações tais como embaralhamento, reversão, ou substituição.

Origens

Seymour Ginsburg da Universidade do Sul da Califórnia e Sheila Greibach da Universidade Harvard apresentaram a primeira dissertação sobre a teoria das FLAs  no oitavo anual IEEE simpósio em comutação e teoria dos autômatos em 1967 .

Referências

• Predefinição:Citar conferência
• Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. Chapter 11: Closure properties of families of languages.
• Predefinição:Citar livro