2012.07.01 22:27
wyrażenie regularne sprawdzające, czy dany napis jest poprawnym wyrażeniem regularnym
Już wiem: nie da się napisać wyrażenia regularnego sprawdzającego, czy dany napis jest poprawnym wyrażeniem regularnym. Bo rekurencja wymaga nieograniczonej pamięci, a każde wyrażenie regularne jest automatem skończonym, a automat skończony ma skończoną liczbę stanów, więc pamięć skończoną.
komentarze:
2012.07.02 07:27 Piotrek
No tak. Ale każde wyrażenie regularne jest gramatyką bezkontekstową, a da się napisać wyrażenie regularne sprawdzające, czy dany napis jest poprawnym opisem pewnej gramatyki bezkontekstowej (w tym standardowym zapisie, jako ciąg reguł postaci A -> gamma). Więc ciekawe. Może istnieje jakiś inny sposób zapisywania wyrażeń regularnych - ale taki, żeby dało się nim zapisywać tylko wyrażenia regularne, a inne gramatyki bezkontekstowe już nie - który dałoby się opisać jakimś wyrażeniem regularnym?
2012.07.09 01:13 Piotrek
Zaraz, zaraz, przecież to proste. Da się sprawdzać wyrażeniem regularnym, czy dany napis jest poprawną gramatyką bezkontekstową, tylko jest jeden problem - że nie da się sprawdzać, czy każdy symbol nieterminalny użyty gdzieś po prawej stronie został zdefiniowany gdzieś po lewej stronie. No ale to można dodać założenie, że niezdefiniowane symbole nieterminalne definiujemy jako rozwijające się do napisu pustego, i wtedy możemy dopuścić używanie po prawej stronie niezdefiniowanych symboli nieterminalnych. A sprawdzać, czy dana gramatyka jest regularna, też jest łatwo - wystarczy sprawdzać, czy prawa strona ma zawsze postać \"ciąg terminali nieterminal\" lub \"nieterminal ciąg terminali\".
powrot na strone glowna
RSS