5.9. Szóprobléma

A reguláris nyelvek esetén a szóprobléma nyagyon hatékonyan megoldható. Ha megszerkesztünk egy az adott nyelvet elfogadó determinisztikus véges automatát, akkor annak segítségével a szót betűnként elolvasva végig követve az automata futását (legkésőbb) a szó végére érve megkapjuk a választ a kérdésre: ha végállapotba jutottunk a szó végén, akkor a szó benne van az adott reguláris nyelvben; ha nem végállapotba jutottunk, vagy (parciális automata esetén) időközben elakadtunk a feldolgozással, akkor a keresett szó nincs a nyelvben.

Tehát a probléma valós időben megoldható, ahány betűből áll az input szó, annyi lépés után tudjuk a választ.

Hasonlóan hatékony algoritmus készíthető, ha G=(N, T, S, H) erős normálformájú reguláris nyelvtannal adott a nyelv. Ekkor egy lineáris felismerési mátrixot készíthetünk (a mátrix mezőibe (celláiba) a nemterminálisok részhalmazai fognak kerülni).

Legyen a w elemzendő szó hossza n, ekkor egy 1 soros n+1 mezőből álló sormátrixot készítünk, a mezőket 0-tól n- ig számozzuk. Az i- edik mező fölé odaírjuk az input szó i- edik betűjét, a i - t, a 0. mezőbe pedig a nyelvtan S mondatszimbólumát.

Ezután a cellákat balról jobbra haladva töltjük ki: az i- edik (0<i<n) cellába beírunk egy A nemterminálist, pontosan akkor ha az (i-1)-edik cellában van olyan B nemterminális, amelyre Ba i AH.

Az n- edik cella kitöltése: akkor írunk egy + jelet a cellába, ha van olyan nemterminális B az (n-1)-edik cellában, melyre Ba n H. A w szó pontosan akor van benne az L(G) generált nyelvben, ha az n- edik cellába + került.

Az ismertetett algoritmus éppen a nemdeterminisztikus üresszóátmenet nélküli automata lehetséges futásait szimulálja az adott bemenő szóra.