Regularni izrazi

Relacije med vhodnimi in izhodnimi besedami avtomata podamo z regularnimi izrazi

Operacije:

• vsota $P+R$ (hkratnost)
  
• produkt $PR$ (zapovrstnost)
  
• iteracija $P^{\ast }=\{P\}=\lambda +P+PP+...$
  

Pravila regularnih izrazov: (vse lahko preverimo z risanjem avtomatov po zgornjih primerih)

• $P+R=R+P$
• $P+(R+Q)=(P+R)+Q$
• $P+P=P$
• $P(RQ)=(PQ)R$
• $(P+R)Q=PQ+RQ$
• $(P^{\ast }{)}^{\ast }=P^{\ast }$
• $P^{\ast }=\lambda +P{P}^{\ast }$
• $P^{\ast }{P}^{\ast }=P^{\ast }$
• $P^{\ast }+P=P^{\ast }$

Pretvorba avtomata v regularni izraz

Gledamo, kako se lahko pomikamo po grafu, možne zanke se predstavi kot iteracije