Família abstrata de linguagens

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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[editar | editar código-fonte]

Uma linguagem formal é um conjunto  para o qual existe um conjunto finito de símbolos abstratos  tais que , onde * é a operação do Fecho de Kleene.

Uma família de linguagens é um par ordenado , onde

  1. é um conjunto infinito de símbolos;
  2. é um conjunto de linguagens formais;
  3. Para cada  em  existe um subconjunto finito  tal que ; e
  4. ≠ Ø para algum  em .

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Referências[editar | editar código-fonte]

  • 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