«Соңғы автоматтар және формальдік тілдер теориясы»

Соңғы автоматтардың эквиваленттілігі. Мур теоремасы

жүктеу 14,81 Mb.

бет	60/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 ... 56 57 58 59 60 61 62 63 ... 127

2. Соңғы автоматтардың эквиваленттілігі. Мур теоремасы.

Егер Ф және Ғ функцияларының екі булевтары барлық мүмкін өзгерістерде бірдей мәнге ие болса, эквивалентті болып табылады. Булевты функциялардың өзгерістері шексіз емес, сондфқтан оларды қарап шығып, Ф және Ғ эквивалентті екендігін тексеруге болады. Егер өзгерістер саны көп болса, Ф және Ғ қалыпты түрге келтіріп, оларды салыстыруға мүмкіндік аламыз. Сонымен қатар Ф және Ғ эквивалентілігін тексеру үшін ФҒ функциясы маңызы бар ма екенін талдауға болады.

Соңғы автоматтарда жағдай басқаша. Егер олардың жүзеге асыратын кіріс-шығыстары эквивалентті болса, екі сонғы автомат та эквивалентті.Соңғы автомат түзілісті кіріс белгілерінің көптеген шығыс түзілісті белгілеріне бейнеленуін жүзеге асырады. Сондықтан автоматты бейнеленулерді олардың мәндерінің барлық мүмкін аргументтерде жай ғана көрсетумен салыстыруға болмайды. Бірнеше анықтамаларды көрсетейік.

Автоматтың кіріс және шығыс функцияларын, олар кіріс алфовитінің көптеген түзілісті белгілері арқылы анықтау үшін, кеңейтейік.

- алфавит (көптеген белгілердің соңы) және

элементтерінің түзілістерінің типтары.

- белгілерді сақтамаған, бос түзіліс, ал ^ – түзілістерді жабыстыру (конкатенация) операциясы. Сөйтіп, aab^ba=aabba. Конкатенация операциясының белгісін көп жағдайда көрсетпейді. Түзілістерді

,... кіші грек әріптерімен белгілейміз.

конкатенация операциясының әрі оң, әрі сол бірлігі екендігі айқын:

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 ... 56 57 58 59 60 61 62 63 ... 127