Nyelvi egyenletrendszerek megoldása, általánosított automata

• Nyelvi egyenletrendszerek megoldása, általánosított automata
  • Lineáris nyelvi egyenletrendszerek megoldása
  • Automata adott állapotra vonatkozó maradéknyelve
  • Általánosított automata
  • Kis Bar-Hillel lemma
  • Források

Lineáris nyelvi egyenletrendszerek megoldása

Arden tétele általánosabban:

Legyenek az $L_1$ és $L_2$ nyelvek adottak. Az X = L_1 X \cup \L_2 egyenletnek $X$-re vonatkozó megoldása $X=L_1^{\ast }L2$. Amennyiben $ϵ\notin L_1$, akkor az egyenletnek ez az egyetlen megoldása.

Legyen $x=Mx\cup v$ nyelvi egyenletrendszer, ahol az $M$ nyelvmátrix és a $v$ nyelvvektor adott az $x$ ismeretlen nyelvekből álló vektort keressük. Ha $$\mathcal{L}={\cup }_{j=1}^n{\cup }_{k=1}^n\{L_{j,k}\}\cup {\cup }_{j=1}^n\{L_j\}\subseteq {\mathcal{L}}_i(i\in \{0,1,2,3\})$$ és $ϵ\notin L_{jk}(1\le j\le n,1\le k\le n)$, akkor az egyenletrendszernek egyértelműen létezik $\mathcal{L}$-beli megoldása, és ez a megoldás $\mathcal{L}$ elemeiből a reguláris nyelvműveletekkel épül fel.

Automata adott állapotra vonatkozó maradéknyelve

Egy $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ determinisztikus véges automata egy $q\in Q$ állapotra vinatkozó maradéknyelve alatt az $L(A,q):=\{v\in {\Sigma }^{\ast }|\delta (q,v)\in F\}$ nyelvet értjük.

Az $L(A,q)$ tehát azokat a $v$ szavakat tartalmazza, amelyek hatására az automata $q$-ból végállapotba kerül.

Tehát $L(A,q_0)=L(A)$ és $ϵ\in L(A,q)⟺q\in F$

Vegyük továbbá észre, hogy fennállnak a következő nyelvi egyenletek:

$$L(a,q)={\cup }_{t\in \Sigma }tL(A,\delta (q,t))\cup \{\varnothing (q\notin F),\{ϵ\}(q\in F)\}$$

ahol $tL:=\{tu|u\in L\}(t\in \Sigma )$

A maradéknyelvekre vonatkozó egyenletrendszert megoldjuk ($L(A,q_0)$ az érdekes). A megoldás egyértelműsége az előző tételből, de az $L(A,q)$-k egyértelműségéből is adódik.

Általánosított automata

Legyen $\mathcal{R}(\Sigma )$ a $\Sigma$ feletti reguláris kifejezések halmaza.

Az általános automata definíciója megegyezik a véges nemdeterminisztikus automata definíciójával azzal a kivétellel, hogy $\delta$ átmenetfüggvényére $\delta :Q\times \mathcal{R}(\Sigma )\to \mathcal{P}(Q)$ teljesül.

Átmenetdiagramon ábrázolva az általánosítás az, hogy az élek címkéi betűk helyett tetszőleges $\Sigma$ feletti reguláris kifejezések lehetnek.

Legyen $A=⟨Q,\sigma ,\delta ,Q_0,F⟩$ egy általánosított automata és legyenek $u,v\in Q{\Sigma }^{\ast }$ konfigurációk. Az $A$ automata az $u$ szót egy lépésben (közvetlenül) a $v$ szóra redukálja (jelölés: $u⟹Av$), ha van olyan $q,p\in Q,z,w\in {\Sigma }^{\ast },R\in \mathcal{R}(\Sigma )$, hogy $p\in \delta (q,R),z\in L(R),u=qzw$ és $v=pw$ teljesül.

A többlépéses redukció és a felismert nyelv fogalma nem változik.

Az $ϵ$-átmenetes, nemdeterminisztikus véges automata olyan általánosított automata, ahol minden átmenet $\Sigma \cup \{ϵ\}$-beli.

Tehát átmenetfüggvénye az input betűnkénti feldolgozása mellett állapotváltásokat engedélyezhet ($ϵ$-átmenetek).

Kis Bar-Hillel lemma

Minden $L\in {\mathcal{L}}_3$ nyelvhez van olyan $n\in \mathbb{N}$ konstans, hogy minden $w\in L$ szó esetén ha tekintjünk egy tetszőleges olyan $w=u{w}^{\prime }v$ felbontását, ahol $|w^{\prime }|\ge n$, akkor van $w^{\prime }$-nek olyan $y$ részszava $(w^{\prime }=xyz)$, hogy $0<|y|\le n$, és minden $i\ge 0$ esetén $ux{y}^{i}zv\in L$.

Kevésbé formálisan: $L$ minden szavának elég hosszú részszavában létezik elég rövid, nemüres, beiterálható részszava.

Források

• Diasor
• Felvétel