Homogenní konečný automat

  • a jsou množiny cílových stavů
  • Jestliže pro všechny dvojice symbolů , platí , pak se automat nazývá homogenní
  • Množiny cílových stavů mají prázdný průnik
  • Tedy když do každého stavu vedou přechody označeny pouze jediným písmenem

../Attachments/Pasted image 20221004170207.png

  • Množiny cílových stavů nám tvoří tzv. rozklad, tedy když je sjednotím, vznikne množina všech stavů
  • Pokud je homogenní NKA, pak počet stavů DKA získaného standardní determinizací (podmnožinovou konstrukcí) je omezen vztahem níže, tedy

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25