Főmenü megnyitása

Módosítások

* ((a|ba(aa)*b)(b(aa)*b)*(a|ba(aa)*b)|b(aa)*b)*(a|ba(aa)*b)(b(aa)*b)* jelöli minden olyan string halmazát, amelyek páros számú ''b''-ből és páratlan számú ''a''-ból állnak. Megjegyezzük, hogy a fenti kifejezés leírható a következő formában is: (''X'' ''Y''*''X'' U ''Y'')*''X'' ''Y''* ahol ''X'' = a|ba(aa)*b és ''Y'' = b(aa)*b.
 
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 komplementer képző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áis 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 [[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.
Lehetséges olyan [[algoritmus]] írása, amelyik két adott reguláris kifejezésről eldönti, hogy az adott nyelven egymásnak megfelelnek-e, ekkor a kifejezéseket egy minimális determinisztikus automatává redukálják, így eldönthető, hogy azok [[izomorf]]ak-e (ekvivalensek).
 
Hogyan lehet megszüntetni a redundanciát? Található-e reguláris kifejezések olyan megfelelő részhalmaza, amely még teljesen kifejező? A Kleene csillag és halmazok uniója nyilvánvalóan szükségesek, de korlátozottan használhatóak. Kiderül, hogy ez a probléma meglepően bonyolult. Egy egyszerű reguláris kifejezésről kiderül, hogy nincs szisztematikus helyettestésihelyettesítési eljárás valamilyen normál formává alakítására. A reguláris kifejezések végesen nem axiomatizálhatók. Más módszert kell igénybe venni. A fentiek miatt merült fel a [[csillag súly probléma]] .
 
A gyakorlatban megvalósított „reguláris kifejezés elemző gépek” működését nem lehet egy reguláris kifejezés algebrával leírni; a részleteket lásd a [[#Minták a szabálytalan nyelvekben|alul]] pontban.
89 974

szerkesztés