Lineáris grammatikák, 3-típusú grammatikák normálformája, reguláriws kifelyezések

• Lineáris grammatikák, 3-típusú grammatikák normálformája, reguláriws kifelyezések
  • Lineáris grammatikák és nyelvek
    • Bal és jobblineáris nyelvek
    • L3 tükrözésre való zártsága
  • 3-típusú grammatikák normálformája
  • Reguláris kifelyezések
    • Leíró erő
    • Arden tétele
  • Források

Lineáris grammatikák és nyelvek

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatikát lineárisnak nevezünk, ha minden szabálya vagy

1. $A\to u,A\in N,u\in {\Sigma }^{\ast }$ vagy
2. $A\to u_{1}B{u}_2$ alakú, ahol $A,B\in N$ és $u_1,u_2\in {\Sigma }^{\ast }$

A $G$ lineáris grammatikát bal-lineárisnak nevezzük, ha minden 2. alakú szabályban $u_1=ϵ$.

A $G$ lineáris grammatikát jobb-lineárisnak nevezünk, ha minden 2. alakú szabályban $u_2=ϵ$.

Bal és jobblineáris nyelvek

Egy $L$ nyelvet lineárisnak, bal-lineárisnak, illyetve jobb-lineárisnak mondunk, ha van olyan $G$ lineáris, bal-lineáris, illetve jobb-lineáris grammatika, amelyre $L=L(G)$ teljesül.

Minden bal-lineáris grammatika reguláris (3-típusú) nyelvet generál.

L3 tükrözésre való zártsága

Minden $G=⟨N,\Sigma ,P,S⟩$ jobb-lineáris grammatikához meg tudunk konstruálni egy $G^{\prime }$ bal-lineáris grammatikát, amely $L(G)$ tükörképét generálja.

Következmény:

1. ${\mathcal{L}}_3$ zárt a tükrözés műveletére nézve.
2. Minden reguláris nyelv generálható bal-lineáris grammatikával.

3-típusú grammatikák normálformája

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatika 3-as normálformájú, ha minden $P$-beli szabály alakja

• $X\to aY,X,Y\in N,a\in \Sigma$ vagy
• $X\to ϵ$, ahol $X\in N$

Minden reguláris (azaz 3-típusú) nyelv generálható 3-as normálformájú grammatikával.

Reguláris kifelyezések

Vegyük észre, hogy minden véges nyelv reguláris. Tudjuk továbbá, hogy az ${\mathcal{L}}_3$ nyelvosztály zárt az unió, a konkatenáció és az iteratív lezárt műveletekre nézve.

Következésképpen, kiindulva véges számú véges nyelvből és az előzőekben felsorolt reguláris műveleteket véges sokszor alkalmazva reguláris nyelvet kapunk.

Kérdés az, hogy vajon az eljárással minden reguláris nyelvet ekő tudunk-e állítani, azaz ez a módszer elégséges-e az ${\mathcal{L}}_3$ nyelvosztály leírására?

Legyenek $V$ és $V^{\prime }=\{\theta ,ϵ,.,+,\ast ,(,)\}$ diszjunkt ábécék. A $V$ ábécé feletti reguláris kifelyezéseket rekurzív módon következőképpen definiáljuk:

• $\theta$ reguláris kifejezés $V$ felett
• $ϵ$ reguláris kifejezés $V$ felett
• $a$ reguláris kifejezés $V$ felett, ha $a\in V$
• Ha $R$ reguláris kifejezés $V$ felett, akkor $R^{\ast }$ is reguláris kifejezés $V$ felett
• Ha $Q$ és $R$ reguláris kifejezések $V$ felett, akkor $(Q\cdot R)$ is
• Ha $Q$ és $R$ reguláris kifejezések $V$ felett, akkor $(Q+R)$ is

Minden egyes $R$ reguláris kifejezés egy-egy $L(R)$-rel jelölt reguláris nyelvet határoz meg, amelyeket az alábbi rekurzióval definiálunk:

1. $L(\theta ):=\theta$
2. $L(ϵ):=\{ϵ\}$
3. $L(a):=\{a\}$
4. $L(R^{\ast }):=L(R{)}^{\ast }$, ha $R$ reguláris kifejezés
5. $L(Q\cdot R):=L(Q)L(R)$, ha $Q,R$ reguláris kifejezések
6. $L(Q+R):=L(Q)\cup L(R)$, ha $Q,R$ reguláris kifejezések

A műveletek precedens sorrendje: $\ast ,.,+$, ennek és az asszociatív szabályok figyelembevételével bizonyos zárójelpárok elhagyhatók.

Leíró erő

Minden reguláris kifejezés reguláris nyelvet ír le, és megfordítva, minden reguláris nyelvhez megadható egy, ezen nyelvet leíró reguláris kifejezés.

Arden tétele

Ezt a tételt később a reguláris kifejezések véges automatákkal való kapcsolatának vizsgálatakor fogjuk használni.

Adottak az $R$ és $Q$ reguláris kifejezések. A $P=R+P\cdot Q$ egyenletnek $P$-re vonatkozó megoldása $P=R\cdot Q^{\ast }$. Amennyiben $ϵ\notin L(Q)$, akkor az egyenletnek ez az egyetlen megoldása.

Források

• Diasor
• Felvétel