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 ${\displaystyle L}$ para o qual existe um conjunto finito de símbolos abstratos ${\displaystyle \Sigma }$ tais que ${\displaystyle L\subseteq \Sigma ^{*}}$, onde * é a operação do Fecho de Kleene.

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

1. ${\displaystyle \Sigma }$ é um conjunto infinito de símbolos;
2. ${\displaystyle \Lambda }$ é um conjunto de linguagens formais;
3. Para cada ${\displaystyle L}$ em ${\displaystyle \Lambda }$ existe um subconjunto finito ${\displaystyle \Sigma _{1}}$ ⊂ ${\displaystyle \Sigma }$ tal que ${\displaystyle L}$ ⊆ ${\displaystyle \Sigma _{1}^{*}}$; e
4. ${\displaystyle L}$ ≠ Ø para algum ${\displaystyle L}$ em ${\displaystyle \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.[1][2]

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.[3]

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 .[4]

Notas

1. Ginsburg (1975)
2. Mateescu, A.; Salomaa, A. (2001), «Abstract family of languages», in: Hazewinkel, Michiel, Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer 
3. Păun, Gh. (2001), «AFL operations», in: Hazewinkel, Michiel, Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer 
4. Ginsburg & Greibach (1967)

Referências

• Ginsburg, Seymour; Greibach, Sheila (1967). «Abstract Families of Languages». Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139 
• 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.
• Mateescu, Alexandru; Salomaa, Arto (1997). «Chapter 4: Aspects of Classical Language Theory». In: Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. [S.l.]: Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9