Főmenü megnyitása

Módosítások

a
A reguláris kifejezések formális definíciói szándékosan a lehető legegyszerűbbek és igyekszenek elkerülni a redundáns mennyiségi jelölőket, (? és +) amelyek kifejezhetőek a következőképpen: ''a''<sup>+</sup>= aa*, és ''a''? = (ε|a). Néha a komplementer képző operátort ~ is használják (~''R'' jelöli az összes string halmazát a Σ ábécé felett, amelyek nem részei ''R''-nek. A komplementerképző operátor redundáns: minden esetben kifejezhető egyéb operátorok használatával.
 
A reguláris kifejezések ebben az értelemben pontosan kifejezhetők a nyelvek azon csoportjával, amelyeket [[véges automata]] el tud fogadni: a [[reguláris nyelv]]ekkel. Némi ellentmondást jelent, hogy a reguláris nyelvek néhány osztálya leírható egy automatával, azonban a reguláris kifejezések hossza [[exponenciális függvény|exponenciálisan növekvő]], míg más esetben a hossz növekedése csak lineáris. A reguláris kifejezések által definiált nyelvek osztálya megfelel a [[Formális_nyelvtanFormális nyelvtan#A_ChomskyA Chomsky-f.C3.A9le_hierarchiaféle hierarchia|Chomsky-féle hierarchia]] harmadik típusú [[Formális nyelvtan|nyelvtanainak]], és leírásukhoz a [[reguláris nyelv]]ek használhatók.
 
Amint azt a példák is mutatják, különböző reguláris kifejezések azonos nyelven kifejezhetők: a használt formalizmus redundáns.
164 908

szerkesztés