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

жүктеу 14,81 Mb.

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

1 ... 64 65 66 67 68 69 70 71 ... 127

Анықтама 3.6.

Мысал 3.2.

Суретте көрсетілгендей екі соңғы автомат қалыптарының саны әр түрлі және бұл қалыптар әр түрлі аталады. Бірақ сырттай қарағанда олардың әрекеттері ұқсас: бірінші автоматтық кіріс түзіліске реакциясы ааbbabb тең

(qо,aabbabb)=

(sо,aabbabb)=0001001.

Алайда автоматтардың барлық кіріс түзілістерге реакцияларына қарсы бұл автоматтар эквивалентті ме деген сұраққа жауап беру мүмкін емес. Сондықтан, соңғы автоматтардың эквиваленттілігі мәселесі тривальді емес.

Бұл мәселені шешудің қарапайым әдісі бар. Әдіс соңғы автоматтардың нақты өндірісі түсінігіне негізделген.

Анықтама 3.6. A=,

> и B=,

> сонғы автоматтың Х кіріс алфавитімен бірдей нақты өндірісі деп A

B= SА

SВ, Х,YА

YВ,( SОА, SОВ),

> автомат аталады, онда:

жүктеу 14,81 Mb.

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

1 ... 64 65 66 67 68 69 70 71 ... 127