2. fejezet - Megoldások

2.1. Reguláris kifejezések

[Megjegyzés]Megjegyzés

A feladatmegoldások során a szorzást (konkatenációt) nem jelöljük.

  1. A reguláris kifejezésben mindenképpen jelölni kell a két a betűt. Ezek előtt, között és mögött tetszőleges számú b szerepelhet: b*ab*ab*.

  2. Jelöljük az első két a betűt. Ezek előtt és között tetszőleges számú b szerepelhet, végül a második a-t bármi követheti: b*ab*a(a+b)*.

  3. Az első megoldáshoz képest az az eltérés, hogy bármely a eltűnhet, így ezeket a+λ-val helyettesítjük: b*(a+λ)b*(a+λ)b*.

  4. Az első két betű bármi lehet, ezt követi a b, majd ezt bármi követheti: (a+b)(a+b)b(a+b)*.

  5. Az első betű bármi lehet, a második csak a vagy c, majd ezt bármi követheti: (a+b+c)(a+c)(a+b+c)*.

  6. Ha a mássalhangzók száma páros, akkor a szót olyan részekre lehet bontani, melyek mássalhangzókkal kezdődnek és pontosan két mássalhangzót tartalmaznak. A két mássalhangzó között és a második mögött tetszőleges számú a betű szerepelhet. Viszont a teljes szó kezdődhet tetszőleges számú a betűvel: a*((b+c)a*(b+c)a*)*.

  7. Mivel a b csakis duplán szerepelhet, a tetszőleges szót leíró reguláris kifejezést kell egy kicsit átírni: (a+bb)*. Más irányból megközelítve a b-k sorozatai között tetszőleges számú a lehet: (a*(bb))*.

  8. Egy elemi konjunkció egy literál vagy literálok konjunkciója, tehát az első literált operátor-literál párosok követik: p(kp)*. A diszjunktív normálforma egy elemi konjunkció vagy azok diszkunkciója, azaz a szerkezet nagyon hasonló. Mivel a diszjunkció és konjunkció azonos precedenciájú, az elemi konjunkciókat zárójelezzük: [p(kp)*](d[p(kp)*])*. A kerek zárójeleknek speciális szerepe van a reguláris kifejezésekben, ezért használunk szögletes zárójeleket. Természetesen az egy literálból álló elemi konjunkciót felesleges zárójelezni, ám ezzel a [p(kp)*] reguláris kifejezés helyett p+[pkp(kp)*]-t kellett volna írni az előbbi megoldásba, amit felesleges elbonyolításnak érzünk.

  9. A szó mindenképpen a betűvel kezdődik, így bontsuk olyan részekre melynek a kezdőbetűje a, és nem tartalmaz újabb a-t. Mivel páros betű nem fordulhat elő a szóban, a kezdő a betűt felváltva követheti b és c tetszőleges hosszan, de legalább egy betűnek kell itt szerepelni, mert a két a-t el kell választani egymástól. Az utolsó rész állhat egy darab a betűből is: (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a. Természetesen létezik más megoldás is, amely egyeseknek egyszerűbbnek tűnhet.