Vzorový jazyk (formální jazyky) - Pattern language (formal languages)

v teoretická informatika, a vzorový jazyk je formální jazyk které lze definovat jako množinu všech konkrétních instancí a tětiva konstant a proměnných. Vzorové jazyky představil Dana Angluin v kontextu strojové učení.^[1]

Definice

Vzhledem k konečné sadě Σ konstantní symboly a spočetná sada X z proměnná symboly nesouvislé od Σ, a vzor je konečný neprázdný tětiva symbolů z Σ∪X.v délka vzoru p, označeno |p|, je pouze počet jeho symbolů. Sada všech vzorků obsahující přesně n odlišné proměnné (každá se může vyskytnout několikrát) jsou označeny P_n, soubor všech vzorů vůbec P_*.A substituce je mapování F: P_* → P_* takhle^{[poznámka 1]}

F je homomorfismus s ohledem na zřetězení řetězce (⋅), formálně: ∀p,q∈P_*. F(p⋅q) = F(p)⋅F(q);
F se nevymazává, formálně: ∀p∈P_*. F(p) ≠ ε, kde ε označuje prázdný řetězec; a
F respektuje konstanty, formálně: ∀s∈Σ. F(s) = s.

Li p = F(q) pro některé vzory p, q ∈ P_* a nějaké substituce F, pak p se říká, že je méně obecné než q, psaný p≤q; v takovém případě nutně |p| ≥ |q| drží. Pro vzor p, své Jazyk je definována jako sada všech méně obecných vzorů, které jsou vytvořeny pouze z konstant, formálně: L(p) = { s ∈ Σ⁺ : s ≤ p }, kde Σ⁺ označuje množinu všech konečných neprázdných řetězců symbolů z Σ.

Například pomocí konstant Σ = {0, 1} a proměnných X = { X, y, z, ...}, vzor 0X10xx1 ∈P₁ a xxy ∈P₂ má délku 7, respektive 3. Instance bývalého vzoru je 00z100z0z1 a 01z101z1z1, získá se substitucí, která mapuje X na 0z a do 1z, respektive každý další symbol sám pro sebe. Oba 00z100z0z1 a 01z101z1z1 jsou také instance xxy. Ve skutečnosti, L(0X10xx1) je podmnožinou L(xxy). Jazyk vzoru X0 a X1 je sada všech bitových řetězců, které označují sudé a liché binární číslo, resp. Jazyk xx je sada všech řetězců, které lze získat zřetězením bitového řetězce se sebou, např. 00, 11, 0101, 1010, 11101110 ∈ L(xx).

Vlastnosti

NP-tvrdost členství ve vzorovém jazyce, podle snížení z NP-kompletní Problém 1 v 3 SAT: Vzhledem k CNF z m doložky s n proměnné, vzor délky 3n+4m+1 s 2n proměnné a řetězec délky 4n + 5m+1 lze zkonstruovat podle obrázku (m= 3 a n= 4 v příkladu). Velkými písmeny proměnné ve vzoru odpovídají negovaným proměnným v CNF. Řetězec odpovídá vzoru právě tehdy, když existuje přiřazení, takže v každé klauzuli je přesně jeden literál 1 (což znamená „skutečný"v CNF). V levé části, např." 0wW0 "se shoduje s" 01110 ", pouze pokud jeden z w,Ž se shoduje s „1“ (odpovídá „Nepravdivé„) a další„ 11 “(odpovídá„skutečný"), tj. pokud w odpovídá negaci Ž. V pravé části, např. „0xYZ0 "se shoduje s" 011110 ", pouze pokud přesně jeden z X,Y,Z odpovídá „11“ a ostatním „1“, tj. pokud přesně jeden literál odpovídá „skutečný".

Problém rozhodování, zda s ∈ L(p) pro libovolný řetězec s ∈ Σ⁺ a vzor p je NP-kompletní (viz obrázek), a tedy i problém rozhodování p ≤ q pro libovolné vzory p, q.^[2]

Třída vzorových jazyků je není zavřeno pod ...

unie: např. pro Σ = {0,1} jako výše, L(01)∪L(10) není vzorový jazyk;
doplněk: Σ⁺ \ L(0) není vzorový jazyk;
průsečík: L(X0y)∩L(X1y) není vzorový jazyk;
Kleene plus: L(0)⁺ není vzorový jazyk;
homomorfismus: F(L(X)) = L(0)⁺ není vzorový jazyk, za předpokladu F(0) = 0 = F(1);
inverzní homomorfismus: F⁻¹(111) = {01, 10, 000} není předpokládaný vzorový jazyk F(0) = 1 a F(1) = 11.

Třída vzorových jazyků je Zavřeno pod ...

zřetězení: L(p)⋅L(q) = L(p⋅q);
obrácení: L(p)^rev = L(p^rev).^[3]

Li p, q ∈ P₁ jsou vzory obsahující přesně jednu proměnnou p ≤ q kdyby a jen kdyby L(p) ⊆ L(q); stejná rovnocennost platí pro vzory stejné délky.^[4]U vzorů různé délky se výše příklad p = 0X10xx1 a q = xxy ukázat to L(p) ⊆ L(q) může držet bez naznačení p ≤ qJakékoli dva vzory p a q, libovolných délek, generují stejný jazyk tehdy a jen tehdy, pokud jsou shodné s konzistentním přejmenováním proměnné.^[5]Každý vzor p je společné zobecnění všech řetězců v jeho generovaném jazyce L(p), modulo asociativita (⋅).

Umístění v Chomského hierarchii

V rafinovaném Chomského hierarchie, třída vzorových jazyků je správná nadtřída a podtřída singletonu^{[poznámka 2]} a indexované jazyky, ale neporovnatelné s jazykovými třídami mezi nimi; kvůli druhému není třída vzorového jazyka v tabulce výslovně uvedena níže.

Třída vzorových jazyků je nesrovnatelná s třídou konečné jazyky, s třídou běžné jazyky a se třídou bezkontextové jazyky:

vzorový jazyk L(xx) není bezkontextový (tedy ani.) pravidelný ani konečný ) v důsledku čerpací lemma;
konečný (tedy také běžný a bezkontextový) jazyk {01, 10} není vzorový jazyk.

Každý singletonový jazyk je triviálně vzorovým jazykem generovaným vzorem bez proměnných.

Každý vzorový jazyk může být vytvořen pomocí indexovaná gramatika: Například pomocí Σ = { A, b, C } a X = { X, y },vzor A X b y C X A y b je generován gramatikou s neterminálními symboly N = { S_X, S_y, S } ∪ X, terminálové symboly T = Σ, indexové symboly F = { A_X, b_X, C_X, A_y, b_y, C_y }, počáteční symbol S_Xa následující pravidla produkce:

S_X[σ]	→ S_X[A_X σ]	\| S_X[b_X σ]	\| S_X[C_X σ]	\| S_y[σ]
S_y[σ]	→ S_y[A_y σ]	\| S_y[b_y σ]	\| S_y[C_y σ]	\| S[σ]
S[σ]	→ A X[σ] b y[σ] C X[σ] A y[σ] b

X[A_X σ]	→ A	X[σ]	y[A_X σ]	→	y[σ]
X[b_X σ]	→ b	X[σ]	y[b_X σ]	→	y[σ]
X[C_X σ]	→ C	X[σ]	y[C_X σ]	→	y[σ]
X[A_y σ]	→	X[σ]	y[A_y σ]	→ A	y[σ]
X[b_y σ]	→	X[σ]	y[b_y σ]	→ b	y[σ]
X[C_y σ]	→	X[σ]	y[C_y σ]	→ C	y[σ]
X[]	→ ε		y[]	→ ε

Příklad odvození je:

S_X[] ⇒ S_X[b_X] ⇒ S_X[A_X b_X] ⇒ S_y[A_X b_X] ⇒ S_y[C_y A_X b_X] ⇒ S[C_y A_X b_X] ⇒ A X[C_y A_X b_X] b y[C_y A_X b_X] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ A X[A_X b_X] b y[C_y A_X b_X] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ A A X[b_X] b y[C_y A_X b_X] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ A ab X[] b y[C_y A_X b_X] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ A ab b y[C_y A_X b_X] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ ... ⇒ A ab b C y[] C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ A ab b C C X[C_y A_X b_X] A y[C_y A_X b_X] b ⇒ ... ⇒ A ab b C C ab X[] A y[C_y A_X b_X] b ⇒ A ab b C C ab A y[C_y A_X b_X] b ⇒ ... ⇒ A ab b C C ab A C y[] b ⇒ A ab b C C ab A C b

Podobným způsobem lze sestavit indexovou gramatiku z jakéhokoli vzoru.

Vzory učení

Vzhledem k ukázkové sadě S řetězců, vzor p je nazýván popisný z S -li S ⊆ L(p), ale ne S ⊆ L(q) ⊂ L(p) pro jakýkoli jiný vzor q.

Vzhledem k jakékoli vzorové sadě S, popisný vzor pro S lze vypočítat pomocí

výčet všech vzorů (až po proměnné přejmenování) ne delší než nejkratší řetězec v S,
výběr z nich vzory, které generují nadmnožinu S,
výběr z nich vzory maximální délky, a
výběr z nich vzor, který je minimální vzhledem k ≤.^[6]

Na základě tohoto algoritmu může být třída vzorových jazyků v limitu z pozitivních příkladů.^[7]

Poznámky

^ Angluinův pojem substituce se liší od obvyklého pojmu substituce řetězce.
^ tj. jazyky skládající se z jednoho řetězce; odpovídají lineární gramatiky

Reference

^ Dana Angluin (1980). Msgstr "Hledání vzorů společných pro sadu řetězců". Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.
^ Věta 3.6, str.50; Dodatek 3.7, s. 52
^ Věta 3.10, s. 53
^ Lemma 3,9, str. 52; Důsledek 3.4, str.50
^ Věta 3.5, str.50
^ Věta 4.1, s. 53
^ Dana Angluin (1980). „Induktivní odvození formálních jazyků z pozitivních dat“ (PDF). Informace a kontrola. 45 (2): 117–135. doi:10.1016 / s0019-9958 (80) 90285-5.; zde: Příklad 1, s. 125

[2] Angluinův pojem substituce se liší od obvyklého pojmu substituce řetězce.

[7] tj. jazyky skládající se z jednoho řetězce; odpovídají lineární gramatiky

[1] Dana Angluin (1980). Msgstr "Hledání vzorů společných pro sadu řetězců". Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.

[3] Věta 3.6, str.50; Dodatek 3.7, s. 52

[4] Věta 3.10, s. 53

[5] Lemma 3,9, str. 52; Důsledek 3.4, str.50

[6] Věta 3.5, str.50

[8] Věta 4.1, s. 53

[9] Dana Angluin (1980). „Induktivní odvození formálních jazyků z pozitivních dat“ (PDF). Informace a kontrola. 45 (2): 117–135. doi:10.1016 / s0019-9958 (80) 90285-5.; zde: Příklad 1, s. 125

[1]

[poznámka 1]

[2]

[3]

[4]

[5]

[poznámka 2]

[6]

[7]