AFL Theory - formallang.memo

Theory of AFL = Abstract Families of Languages

言語の演算に対する性質を調べる理論

• 参考資料: http://eom.springer.de/A/a110110.htm
• 起源は Seymour Ginsburg, Sheila Greibach: "Abstract families of languages", Proc. Eighth Annual Symposium on Switching and Automata Theory, 1967 らしい

新しい形式言語システムを定義したときに、「Full AFL になっている（から性質がよい）
」といった形の主張がされたりする。「Full AFLならば必ずこのClosure Propertyが成り立つ」みたいな一般的な定理も色々示されているので、そういう意味で便利。

よく対象とされる演算

• ∪: Union
• @: Concatenation
• *: Kleene star
  • +: Kleene plus
• H: Homomorphism
  • eH: ε-free horomorphism (h(x)=ε => x=ε なhomomorphism)
• iH: Inverse homomorphism
• RG: Intersection with regular sets

代表的なクラス

• Trio
  • eH, iH, RG
• Full Trio (Coneとも呼ばれる)
  • H, iH, RG
• Semi-AFL
  • ∪, eH, iH, RG
• Full Semi-AFL
  • ∪, H, iH, RG
• AFL
  • @, +, ∪, eH, iH, RG
• Full AFL
  • @, *, ∪, H, iH, RG

Full- は e-free な演算に限るか一般的なのを許すかが違い。
Full AFL では ∪ を考えるけれど、∩ や ～ に関して閉じているという性質は無くても許される。文脈自由言語を含んで ∩ に関して閉じさせると空かどうかの判定がundecidableという厄介なクラスになるのであまり考えないんじゃないかなーと予想。

Principal

言語族 F が Principal (Trio/semi-AFL/AFL) であるとは、ある L ∈ F が存在して、F が L を含む最小の(Trio/semi-AFL/AFL)になっていることを言う。L を F の generator という。

---