Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata
Legyen G = (N, Ʃ, P, S) 3-típusú nyelvtan. Ekkor van olyan G' = (N', Ʃ, P', S) 3-típusú nyelvtan, amelyre L(G) = L(G'), és P'-ben minden szabály A → aB vagy A → a alakú (A → λ is megengedett), ahol A, B ∈ N és a ∈ Ʃ.5
A szabály hosszredukció végrehajtásához adjuk hozzá a „Feldolgozás műveletei” listához a „Szabály hosszredukció” elemet. A szabály végrehajtása a „feldolgozás” gomb megnyomására történik. A szabály lefutása során kiírja az indulási állapotot és a lefutás utáni eredmény állapotot.
A szabály hosszredukció algoritmus megkeresi az összes olyan szabályt, amelynek jobb oldalán minimum 3 tagból áll. Ezeket a szabályokat alakítja át úgy, hogy a minden szabály amely a szabály halmazban található maximum 2 tagból álljon.
A megtalált minimum 3 tagból álló szabályokat először leellenőrzi, hogy valamely 2 tetszőleges tagját tudja-e helyettesíteni egy már meglévő olyan szabállyal, amely bal oldali NT tagjához csak pontosan egy azonos szabály tartozik. A műveletet addig folytatjuk, amíg minden szabály maximum 2 tagból áll.
Átalakítandó szabály halmaz:
A → SAB | a <-- Az itt lévő 3 tagú szabályt át kell alakítani! Az utolsó 2 tagot (AB) helyettesítjük a létrehozott új szabállyal (C) B → S | b S → λ | AB
Átalakított szabály halmaz:
A → SC | a B → S | b S → λ | AB C → AB