Běžný jazyk - Regular language

Pro přirozený jazyk, který je regulován, viz Seznam jazykových regulačních orgánů.
„Kleenova věta“ přeadresuje tady. Jeho věty o rekurzivních funkcích viz Kleenova věta o rekurzi.

v teoretická informatika a teorie formálního jazyka, a běžný jazyk (také nazývaný a racionální jazyk)[1][2] je formální jazyk které lze vyjádřit pomocí a regulární výraz, ve striktním smyslu druhého pojmu používaného v teoretické informatice (na rozdíl od mnoha motorů regulárních výrazů poskytovaných moderními programovacími jazyky, které jsou rozšířené o funkce které umožňují rozpoznávání jazyků, které nelze vyjádřit klasickým regulárním výrazem).

Alternativně lze běžný jazyk definovat jako jazyk rozpoznávaný a konečný automat. Ekvivalence regulárních výrazů a konečných automatů je známá jako Kleeneova věta[3] (po americkém matematikovi Stephen Cole Kleene ). V Chomského hierarchie, běžné jazyky jsou definovány jako jazyky generované gramatikami typu 3 (běžné gramatiky ).

Běžné jazyky jsou zvláště užitečné při zadávání analýza a programovací jazyk design.

Formální definice

Sbírka běžných jazyků přes internet abeceda Σ je definován rekurzivně takto:

  • Prázdný jazyk Ø a prázdný jazyk řetězce {ε} jsou běžné jazyky.
  • Pro každého A ∈ Σ (A patří do Σ), jedináček Jazyk {A} je běžný jazyk.
  • Li A a B jsou tedy běžné jazyky A ∪ B (svaz), A • B (zřetězení) a A* (Kleene hvězda ) jsou běžné jazyky.
  • Žádné jiné jazyky nad Σ nejsou běžné.

Vidět regulární výraz pro jeho syntaxi a sémantiku. Všimněte si, že výše uvedené případy jsou ve skutečnosti definujícími pravidly regulárního výrazu.

Příklady

Všechny konečné jazyky jsou pravidelné; zejména prázdný řetězec jazyk {ε} = Ø * je běžný. Mezi další typické příklady patří jazyk skládající se ze všech řetězců nad abecedou {A, b} které obsahují sudý počet As nebo jazyk skládající se ze všech řetězců formuláře: několik As následuje několik bs.

Jednoduchým příkladem jazyka, který není běžný, je sada řetězců { Anbn | n ≥ 0 }.[4] Intuitivně to nelze s konečným automatem rozpoznat, protože konečný automat má konečnou paměť a nedokáže si pamatovat přesný počet a. Jsou uvedeny techniky, jak tuto skutečnost důsledně dokázat níže.

Ekvivalentní formalizmy

Normální jazyk splňuje následující ekvivalentní vlastnosti:

  1. je to jazyk regulárního výrazu (podle výše uvedené definice)
  2. je to jazyk přijímaný a nedeterministický konečný automat (NFA)[poznámka 1][poznámka 2]
  3. je to jazyk přijímaný a deterministický konečný automat (DFA)[Poznámka 3][poznámka 4]
  4. to může být generováno a běžná gramatika[poznámka 5][poznámka 6]
  5. je to jazyk přijímaný organizací střídavý konečný automat
  6. je to jazyk přijímaný a obousměrný konečný automat
  7. to může být generováno a předpona gramatiky
  8. lze ji přijmout pouze ke čtení Turingův stroj
  9. lze jej definovat v monadický logika druhého řádu (Věta Büchi – Elgot – Trakhtenbrot )[5]
  10. to je uznáno nějakým konečným syntaktický monoid M, což znamená, že je preimage { w ∈ Σ* | F(w) ∈ S } podmnožiny S konečného monoidu M pod monoidní homomorfismus F: Σ* → M z volný monoid na jeho abecedě[poznámka 7]
  11. počet tříd rovnocennosti syntaktická kongruence je konečný.[poznámka 8][poznámka 9] (Toto číslo se rovná počtu stavů minimální deterministický konečný automat přijímání L.)

Vlastnosti 10. a 11. jsou čistě algebraické přístupy k definování regulárních jazyků; podobný soubor prohlášení lze formulovat pro monoid M ⊆ Σ*. V tomto případě ekvivalence nad M vede ke konceptu rozpoznatelného jazyka.

Někteří autoři používají jednu z výše uvedených vlastností odlišnou od „1.“ jako alternativní definice běžných jazyků.

Některé z výše uvedených ekvivalentů, zejména ty z prvních čtyř formalizmů, se nazývají Kleeneova věta v učebnicích. Přesně který z nich (nebo která podmnožina) se nazývá takový, se u jednotlivých autorů liší. Jedna učebnice nazývá ekvivalenci regulárních výrazů a NFA („1.“ a „2.“ výše) „Kleeneova věta“.[6] Další učebnice nazývá ekvivalenci regulárních výrazů a DFA („1.“ a „3.“ výše) „Kleeneova věta“.[7] Dvě další učebnice nejdříve dokazují expresivní ekvivalenci NFA a DFA („2.“ a „3.“) a poté uvádějí „Kleeneovu větu“ jako ekvivalenci mezi regulárními výrazy a konečnými automaty (ten uváděl „rozpoznatelné jazyky“) .[2][8] Jazykově orientovaný text nejprve srovnává regulární gramatiky („4.“ výše) s DFA a NFA, volá jazyky generované (některým z těchto) těchto „regulárních“, poté zavádí regulární výrazy, které označuje jako „racionální jazyky“, a nakonec uvádí „Kleeneovu větu“ jako shodu regulárních a racionálních jazyků.[9] Jiní autoři jednoduše definovat „racionální výraz“ a „regulární výrazy“ jsou synonyma a totéž platí pro „racionální jazyky“ a „regulární jazyky“.[1][2]

Vlastnosti uzavření

Běžné jazyky jsou Zavřeno v rámci různých operací, tedy pokud jde o jazyky K. a L jsou pravidelné, tak je výsledkem následujících operací:

  • množina teoretických booleovských operací: svaz K. ∪ L, průsečík K. ∩ L, a doplněk L, tedy také relativní doplněk K. - L.[10]
  • pravidelné operace: K. ∪ L, zřetězení K. ∘ L, a Kleene hvězda L*.[11]
  • the trio operace: řetězový homomorfismus, inverzní řetězcový homomorfismus a průnik s běžnými jazyky. V důsledku toho jsou uzavřeny na základě svévolnosti transdukce konečných stavů, jako kvocient K. / L s běžným jazykem. Ještě více, běžné jazyky jsou uzavřeny pod kvocienty s libovolný jazyky: Pokud L je tedy normální L / K. je pravidelná pro všechny K..[Citace je zapotřebí ]
  • opačný (nebo zrcadlový obraz) LR.[12] Vzhledem k nedeterministickému konečnému automatu k rozpoznání L, automat pro LR lze získat obrácením všech přechodů a záměnou počátečních a koncových stavů. To může mít za následek více počátečních stavů; K jejich připojení lze použít ε-přechody.

Vlastnosti rozhodovatelnosti

Vzhledem ke dvěma deterministickým konečným automatům A a B, je rozhodující, zda přijímají stejný jazyk.[13]V důsledku toho pomocí výše uzavírací vlastnosti, následující problémy jsou také rozhodnutelné pro libovolně dané deterministické konečné automaty A a B, s přijatými jazyky LA a LB, respektive:

  • Zadržení: je LA ⊆ LB ?[poznámka 10]
  • Disjunktnost: je LA ∩ LB = {} ?
  • Prázdnota: je LA = {} ?
  • Univerzálnost: je LA = Σ* ?
  • Členství: dané A ∈ Σ*, je A ∈ LB ?

U regulárních výrazů je problém univerzálnosti NP-kompletní již pro singletonovou abecedu.[14]U větších abeced je to problém PSPACE - kompletní.[15] Pokud jsou regulární výrazy rozšířeny tak, aby umožňovaly i a operátor kvadratury„s“A2„označující totéž jako“AA", stále lze popsat pouze běžné jazyky, ale problém univerzálnosti má dolní hranici exponenciálního prostoru,[16][17][18] a je ve skutečnosti kompletní pro exponenciální prostor s ohledem na redukci polynomiálního času.[19]

Výsledky složitosti

v teorie výpočetní složitosti, třída složitosti všech běžných jazyků se někdy označuje jako PRAVIDELNÝ nebo REG a rovná se DSPACE (O (1)), rozhodovací problémy které lze vyřešit v konstantním prostoru (použitý prostor je nezávislý na velikosti vstupu). PRAVIDELNÝ ≠ AC0, protože (triviálně) obsahuje problém parity při určování, zda je počet 1 bitů na vstupu sudý nebo lichý a tento problém není v AC0.[20] Na druhou stranu, PRAVIDELNÝ neobsahuje AC0, protože nepravidelný jazyk jazyka palindromy nebo nepravidelný jazyk lze rozpoznat v AC0.[21]

Pokud je jazyk ne běžné, vyžaduje stroj minimálně Ω (log log n) prostor k rozpoznání (kde n je velikost vstupu).[22] Jinými slovy, DSPACE (Ó (log log n)) se rovná třídě běžných jazyků. V praxi je většina nepravidelných problémů řešena tím, že stroje zabírají alespoň logaritmický prostor.

Umístění v Chomského hierarchii

Běžný jazyk ve třídách Chomského hierarchie.

Chcete-li najít běžné jazyky v Chomského hierarchie, člověk si všimne, že každý běžný jazyk je bez kontextu. Konverzace není pravdivá: například jazyk skládající se ze všech řetězců se stejným počtem Aje jako bJe bezkontextový, ale není běžný. K prokázání, že jazyk není pravidelný, se často používá Věta Myhill – Nerode a čerpací lemma. Mezi další přístupy patří použití uzavírací vlastnosti běžných jazyků[23] nebo kvantifikovat Kolmogorovova složitost.[24]

Mezi důležité podtřídy běžných jazyků patří

Počet slov v běžném jazyce

Nechat označte počet slov délky v . The obyčejná generující funkce pro L je formální mocenské řady

Generující funkce jazyka L je racionální funkce -li L je pravidelný.[27] Proto pro každý běžný jazyk sekvence je konstantní rekurzivní; to znamená, že existuje celočíselná konstanta , komplexní konstanty a složité polynomy tak, že pro každého číslo slov délky v je.[28][29][30][31]

Tedy nepravidelnost určitých jazyků lze prokázat spočítáním slov dané délky v. Zvažte například Dyck jazyk řetězců vyvážených závorek. Počet slov délky v jazyce Dyck se rovná Katalánské číslo , který nemá formu , svědky nepravidelnosti jazyka Dyck. Je nutné postupovat opatrně, protože některé z vlastních čísel může mít stejnou velikost. Například počet slov délky v jazyce všech sudých binárních slov nemá formu , ale počet slov sudé nebo liché délky má tento tvar; odpovídající vlastní čísla jsou . Obecně platí, že pro každý běžný jazyk existuje konstanta takové, že pro všechny , počet slov délky je asymptoticky .[32]

The funkce zeta jazyka L je[27]

Funkce zeta běžného jazyka není obecně racionální, ale je libovolná cyklický jazyk je.[33][34]

Zobecnění

Pojem regulárního jazyka byl zobecněn na nekonečná slova (viz ω-automaty ) a na stromy (viz stromový automat ).

Racionální sada zobecňuje pojem (běžného / racionálního jazyka) na monoidy, které nemusí být nutně volný, uvolnit. Podobně má pojem rozpoznatelného jazyka (konečným automatem) jmenovce jako rozeznatelná sada přes monoid, který není nutně zdarma. Howard Straubing ve vztahu k těmto skutečnostem poznamenává, že „pojem„ běžný jazyk “je trochu nešťastný. Články ovlivněné Eilenberg monografie[35] často používají buď výraz „rozpoznatelný jazyk“, který odkazuje na chování automatů, nebo „racionální jazyk“, který odkazuje na důležité analogie mezi regulárními výrazy a racionálními řadami sil. (Ve skutečnosti Eilenberg definuje racionální a rozeznatelné podmnožiny libovolných monoidů; tyto dva pojmy se obecně neshodují.) Tato terminologie, i když je lépe motivovaná, nikdy se opravdu neuchytila ​​a „běžný jazyk“ se používá téměř univerzálně. “[36]

Racionální řada je další zobecnění, tentokrát v kontextu a formální mocenské řady během semirování. Tento přístup vede k vážené racionální výrazy a vážené automaty. V tomto algebraickém kontextu jsou běžné jazyky (odpovídající Booleovský -vážené racionální výrazy) se obvykle nazývají racionální jazyky.[37][38] Také v této souvislosti najde Kleeneova věta zevšeobecnění zvané Kleene-Schützenbergerova věta.

Indukce

Hlavní článek: Uvedení běžných jazyků

Poznámky

  1. ^ 1. ⇒ 2. podle Thompsonův konstrukční algoritmus
  2. ^ 2. ⇒ 1. podle Kleenův algoritmus nebo pomocí Ardenovo lemma
  3. ^ 2. ⇒ 3. podle konstrukce výkonové sady
  4. ^ 3. ⇒ 2. od prvního definice je silnější než druhý
  5. ^ 2. ⇒ 4. viz Hopcroft, Ullman (1979), Věta 9.2, s. 219
  6. ^ 4. ⇒ 2. viz Hopcroft, Ullman (1979), Věta 9.1, s. 218
  7. ^ 3. ⇔ 10. podle Věta Myhill – Nerode
  8. ^ u~proti je definován jako: uw∈L kdyby a jen kdyby vw∈L pro všechny w∈Σ*
  9. ^ 3. ⇔ 11. viz důkaz v dokumentu Syntaktický monoid článek a viz str.160 v Holcombe, W.M.L. (1982). Teorie algebraických automatů. Cambridge studia pokročilé matematiky. 1. Cambridge University Press. ISBN  0-521-60492-3. Zbl  0489.68046.
  10. ^ Zkontrolujte, zda LA ∩ LB = LA. Rozhodování o této vlastnosti je NP-tvrdé obecně; vidět Soubor: RegSubsetNP.pdf pro ilustraci důkazního nápadu.

Reference

  1. ^ A b Ruslan Mitkov (2003). Oxfordská příručka počítačové lingvistiky. Oxford University Press. p. 754. ISBN  978-0-19-927634-9.
  2. ^ A b C Mark V. Lawson (2003). Konečné automaty. CRC Press. 98–103. ISBN  978-1-58488-255-8.
  3. ^ Sheng Yu (1997). „Běžné jazyky“. V Grzegorz Rozenberg; Arto Salomaa (eds.). Příručka formálních jazyků: Svazek 1. Slovo, jazyk, gramatika. Springer. p. 41. ISBN  978-3-540-60420-4.
  4. ^ Eilenberg (1974), str. 16 (příklad II, 2.8) a str. 25 (příklad II, 5.2).
  5. ^ M. Weyer: Kapitola 12 - Rozhodnutelnost S1S a S2S, str. 219, Věta 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Přednášky z informatiky 2500, Springer 2002.
  6. ^ Robert Sedgewick; Kevin Daniel Wayne (2011). Algoritmy. Addison-Wesley Professional. p. 794. ISBN  978-0-321-57351-3.
  7. ^ Jean-Paul Allouche; Jeffrey Shallit (2003). Automatické sekvence: Teorie, Aplikace, Zobecnění. Cambridge University Press. p. 129. ISBN  978-0-521-82332-6.
  8. ^ Kenneth Rosen (2011). Diskrétní matematika a její aplikace 7. vydání. McGraw-Hill Science. str. 873–880.
  9. ^ Horst Bunke; Alberto Sanfeliu (leden 1990). Syntaktické a strukturní rozpoznávání vzorů: teorie a aplikace. World Scientific. p. 248. ISBN  978-9971-5-0566-0.
  10. ^ Salomaa (1981), s. 28
  11. ^ Salomaa (1981), s. 27
  12. ^ Hopcroft, Ullman (1979), kapitola 3, cvičení 3,4 g, s. 72
  13. ^ Hopcroft, Ullman (1979), Theorem 3.8, str. 64; viz také Věta 3.10, s. 67
  14. ^ Aho, Hopcroft, Ullman (1974), Cvičení 10.14, s. 401
  15. ^ Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
  16. ^ Hopcroft, Ullman (1979), Theorem 13.15, str. 351
  17. ^ A.R. Meyer & L. J. Stockmeyer (říjen 1972). Problém ekvivalence pro regulární výrazy se čtvercem vyžaduje exponenciální prostor (PDF). 13. ročník IEEE Symp. o teorii přepínání a automatů. 125–129.
  18. ^ L.J. Stockmeyer & A.R. Meyer (1973). Slovní úlohy vyžadující exponenciální čas (PDF). Proc. 5. ann. symp. o teorii výpočtu (STOC). ACM. s. 1–9.
  19. ^ Hopcroft, Ullman (1979), Dodatek str. 353
  20. ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parita, obvody a hierarchie polynomiálního času". Teorie matematických systémů. 17 (1): 13–27. doi:10.1007 / BF01744431. PAN  0738749.
  21. ^ Cook, Stephen; Nguyen, Phuong (2010). Logické základy složitosti důkazů (1. vyd. Vyd.). Ithaca, NY: Sdružení pro symbolickou logiku. p. 75. ISBN  978-0-521-51729-4.
  22. ^ J. Hartmanis, P. L. Lewis II a R. E. Stearns. Hierarchie výpočtů s omezenou pamětí. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, str. 179–190. 1965.
  23. ^ „Jak dokázat, že jazyk není pravidelný?“. cs.stackexchange.com. Citováno 10. dubna 2018.
  24. ^ Hromkovič, Juraj (2004). Teoretická informatika: Úvod do automatů, vypočítatelnosti, složitosti, algoritmizace, randomizace, komunikace a kryptografie. Springer. str. 76–77. ISBN  3-540-14015-8. OCLC  53007120.
  25. ^ Konečný jazyk by neměl být zaměňován s (obvykle nekonečným) jazykem generovaným konečným automatem.
  26. ^ Volker Diekert; Paul Gastin (2008). „Definovatelné jazyky prvního řádu“ (PDF). V Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Logika a automaty: historie a perspektivy. Amsterdam University Press. ISBN  978-90-5356-576-6.
  27. ^ A b Honkala, Juha (1989). Msgstr "Nutná podmínka pro racionalitu funkce zeta běžného jazyka". Teor. Comput. Sci. 66 (3): 341–347. doi:10.1016 / 0304-3975 (89) 90159-x. Zbl  0675.68034.
  28. ^ Flajolet & Sedgweick, oddíl V.3.1, rovnice (13).
  29. ^ "Počet slov v běžném jazyce $ (00) ^ * $". cs.stackexchange.com. Citováno 10. dubna 2018.
  30. ^ Důkaz věty pro libovolné DFA
  31. ^ "Počet slov dané délky v běžném jazyce". cs.stackexchange.com. Citováno 10. dubna 2018.
  32. ^ Flajolet & Sedgewick (2002) Theorem V.3
  33. ^ Berstel, Jean; Reutenauer, Christophe (1990). "Zeta funkce formálních jazyků". Trans. Dopoledne. Matematika. Soc. 321 (2): 533–546. CiteSeerX  10.1.1.309.3005. doi:10.1090 / s0002-9947-1990-0998123-x. Zbl  0797.68092.
  34. ^ Berstel & Reutenauer (2011) str.222
  35. ^ Samuel Eilenberg. Automaty, jazyky a stroje. Akademický tisk. ve dvou svazcích „A“ (1974, ISBN  9780080873749) a „B“ (1976, ISBN  9780080873756), druhá se dvěma kapitolami Breta Tilsona.
  36. ^ Straubing, Howard (1994). Konečné automaty, formální logika a složitost obvodů. Pokrok v teoretické informatice. Basilej: Birkhäuser. p.8. ISBN  3-7643-3719-2. Zbl  0816.68086.
  37. ^ Berstel & Reutenauer (2011), s. 47
  38. ^ Sakarovitch, Jacques (2009). Základy teorie automatů. Z francouzštiny přeložil Reuben Thomas. Cambridge: Cambridge University Press. p. 86. ISBN  978-0-521-84425-3. Zbl  1188.68177.

Další čtení

  • Kleene, S.C.: Zastoupení událostí v nervových sítích a konečných automatech. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, s. 3–41. Princeton University Press, Princeton (1956); je to mírně upravená verze jeho 1951 RAND Corporation zpráva se stejným názvem, RM704.
  • Sakarovitch, J (1987). „Kleeneova věta se vrátila“. Přednášky z informatiky. 1987: 39–50. doi:10.1007/3540185356_29. ISBN  978-3-540-18535-2. Citovat deník vyžaduje | deník = (Pomoc)

externí odkazy