[Javalist] RegExp probléma: nem aposztrófok közé zártak felismerése

[Peter Verhas]

Ha stack kell, akkor nem véges automata. Ha nem véges automata, akkor nem regex. 

—
Dipl. Ing. Peter Verhas

On Mon, Dec 2, 2013 at 11:12 AM, Tamás Viktor <viktor.tamas at gmail.com>
wrote:

> Helló,
> "A reguláris kifejezések és a véges automaták ugyanazokat a nyelveket
> tudják modellezni."
> Ez igaz, viszont ehhez a konkrét feladathoz szerintem egy stack-et kell
> fenntartani, ha valóban matematikailag teljes körű megoldásra van szükség.
> Beugrott, hogy ezek a Chomsky osztályok:
> http://en.wikipedia.org/wiki/Chomsky_hierarchy
> Nekem talán Bach Iván tanította.
> V
> 2013/12/2 Peter Verhas <peter at verhas.com>
>> A reguláris kifejezések és a véges automaták ugyanazokat a nyelveket
>> tudják modellezni.
>>
>> A Context Free Language kategória az, amiből több osztály is van.
>>
>> A konkrét feladatra nem hiszem, hogy külön kellene választani a lexikális
>> elemzőt és a szintaktikus elemzőt. Ezeket azért szokták, mert általában az
>> elemzett nyelvek CF nyelvtannal írható le, és a nyelvtan sokkal egyszerűbb
>> ha egy olyan ABC felett kell csak leírni, amely nem a karaktereket, hanem a
>> tokeneket tartalmazza. A tokenek pedig egy véges automatával leírható
>> nyelvtannal parsolhatók a karaktereket tartalmazó ABC felett. Így két
>> nyelvtant használunk egymás után egy helyett, viszont a kettő egyenként és
>> együtt is sokkal egyszerűbb, mint az eredeti lett volna. Ezen okból
>> kifolyólag a konkrét futás erőforrás igénye is sokkal kisebb.
>>
>> Story:
>>
>> Babai László tartott előadást reguáris kifejezésekről, és véges
>> automatákról a BME-n (http://en.wikipedia.org/wiki/L%C3%A1szl%C3%B3_Babai)
>> és azzal fejezte be az előadást, hogy milyen érdekesek és praktikusak ezek
>> a reguláris kifejezések, és milyen érdekes, hogy informatikában sehol nem
>> használják. (Nem ma volt, de azért Lex, Yacc, Perl... az még éppen nem
>> volt, de volt awk!) Tőlünk tudta meg, hogy de.
>>
>> --
>> Dipl. Ing. Peter Verhas
>> peter at verhas.ch
>> skype: verhas
>> Mobile: +41 79 154 2095
>> Arbeit: +41 44 239 8450
>>
>>
>> Quoting "Tamás Viktor" <viktor.tamas at gmail.com>:
>>
>>  Már nem nagyon emlékszem a formális nyelvekre, de az dereng, hogy a véges
>>> automatával processzálható nyelveknek is van több osztálya és a regex az
>>> egyszerűbbet képes feldolgozni.
>>>
>>>
>> ----------------------------------------------------------------
>> This message was sent using IMP, the Internet Messaging Program.
>> _______________________________________________
>> Javalist mailing list
>> Javalist at lists.javaforum.hu
>> http://lists.javaforum.hu/mailman/listinfo/javalist
>>
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.javaforum.hu/pipermail/javalist/attachments/20131202/aeeb1b9a/attachment.html>