Der kanonischer Automat

Definition

Sei $L\subseteq {\Sigma }^{\ast }$ eine Reguläre Sprache. (sodass Die Nerode-Rechtskongruenz ${\simeq }_L$ einen endlichen Index hat)
Der kanonische DEA $A_L=(Q,\Sigma ,q_s,\delta ,F)$ zu L ist definiert durch:

• $Q:=\{[u{]}_L|u\in {\Sigma }^{\ast }\}$
• $q_s:=[\epsilon {]}_L$
• $\delta ([u{]}_L,a):=[ua{]}_L$
• $F:=[u{]}_L|u\in L$

siehe auch kanonisch

Satz

kanonischer-DEA ist ein minimaler DEA

Beweis

siehe auch:

• Satz von Myhill und Nerode
• Isomorphie von DEAs
• Isomorphie kanonischer DEA und reduzierter DEA