1.3. Abstraktná syntéza

Udalosť, ktorú rozoznáva niektorý konečný automat je regulárna udalosť. Pre regulárne udalosti platí:

  1. {} a (prázdna množina) sú regulárne udalosti.
  2. Každá jednoprvková množina {X}, kde XX a X je konečná množina symbolov, je regulárna udalosť.
  3. Ak udalosti E a G sú regulárne, potom aj EG (alebo E+G) je regulárna udalosť. EG sa nazýva zjednotenie udalostí E a G.
  4. Ak udalosti E a G sú regulárne, potom aj E.G = {e.g| eE, gG} je regulárna udalosť. E.G sa nazýva zreťazenie udalostí E a G a je to množina všetkých slov, ktoré vzniknú zreťazením slov z E a G.
  5. Ak udalosť E je regulárna, potom aj E* = {} E E.E E.E.E ... je regulárna udalosť. E* sa nazýva iterácia udalosti E.
  6. Existujú len také regulárne udalosti, ktoré sú zostavené podľa bodov 1 až 5.

Využitím množinových operácií , ., * možno regulárne udalosti vyjadriť pomocou formúl, v ktorých sa udalosti spájajú uvedenými operáciami. Prostredníctvom nich možno nekonečné množiny slov vyjadriť formulami s konečným počtom prvkov. Tieto formuly sa nazývajú regulárne výrazy. Tie sa dajú použiť ako prechodný krok pri odvádzaní tabuliek prechodov a výstupov zo slovného popisu úlohy.
Určitá udalosť môže byť popísaná ľubovoľným počtom regulárnych výrazov. Tieto sú navzájom ekvivalentné. Pri úpravách a zjednodušovaní ekvivalentných regulárnych výrazov sa používajú určité pravidlá, ktoré predstavujú vzťahy medzi výrazmi. Regulárne udalosti sú práve tie udalosti, pre ktoré existuje regulárny výraz.