Ответи - Страница 2

1-> (DE) (BC) (A) - от тях можете да преминете през същия символ до (D, E)

Изграждане на нова държавна машина (DE) (BC) (A)

една съща

Билет номер 6. Абстрактен автомат. Еквивалентност на автомати.

Състоянието q на автомата M и състоянието q1 на автомата M1 се считат за еквивалентни, ако и двата автомата, получили една и съща (която и да е) входна последователност от символи, го обработват в една и съща изходна последователност.

Автоматите M и M1 се наричат ​​еквивалентни, ако за всяко състояние на автомата M има еквивалентно състояние на автомата M1 и обратно.

С други думи, еквивалентните автомати изпълняват същите трансформации, но могат да имат различен брой вътрешни състояния.

Концепцията за еквивалентност на състоянията е приложима и за един автомат (формално можем да приемем, че M и M1 съвпадат). За един автомат различните състояния ще бъдат еквивалентни, чрез които една и съща последователност от символи се преобразува в един и същ изход.

Автомат, еквивалентен на даден и имащ най-малкото от всички възможни брой състояния, се нарича минимум.

Еквивалентност на крайни автомати

Определение. Два автомати M1 = (Q1, , 1, q10, F1) и M1 = (Q2, , 2, q20, F2) се наричат ​​еквивалентни, ако разпознават един и същ език над азбуката .