Маъруза Мавзу: Компилятор-Чекли автоматлар. Режа

М2 чекли детерминирланган М1 га мос келувчи ўша тилни қабул қилувчи автомат мавжуд. М2 автоматнинг ўтишлари кейинги жадвалда ва расмда келтирилган.

• М2 чекли детерминирланган М1 га мос келувчи ўша тилни қабул қилувчи автомат мавжуд. М2 автоматнинг ўтишлари кейинги жадвалда ва расмда келтирилган.
• M2 = ( К2, ∑2, δ2 , S2 , f2 ).
• К2={A,B,C} , 2={1,0}, S2={A}, f2={B}

Чекли автоматлар.

Холатлар
Кириш		А	B	C
	0	C	B	C
	1	В	B	C

• М2 детерминирланган чекли автоматнинг ўтишлари.

G1 грамматикада генерация қилинган ва қуйидаги туғилувчи қоидалар ёрдамида аниқланган қаторлар А  1А| 1В | 1 В  0В| 1В | 0 | 1 Бу ерда А бошланғич белги бўлиб, М1 ва М2 ёрдамида англанади. Грамматикани детерминирланмаган чекли М1 автоматдан қуйидагича олинади:

1. Автоматнинг бошланғич ҳолати грамматика гапининг бошланғич белгиси бўлади. 2. δ(А,1) =А, δ(В,0)=В δ(А,1) =В, δ(В,1)=B ўтишларга қуйидаги туғилувчи қоидалар мос келади: А  1А| 1В В  0В| 1В А ҳолатда 1 ни ўқишда охирги В ҳолатга ўтиш А  1 га мос келади ва аналогик равишда В  0 | 1 Худди шундай, грамматикадан М1 автоматни келтириб чиқариш мумкин.

1. Детерминированные конечные автоматы (DFA) 1.1. Особенности: В DFA, учитывая текущее состояние, мы можем узнать следующее состояние. Следующее состояние определяется однозначно. Выберите любой ввод символа из пространства символов, и всегда будет уникальное следующее состояние. Например, на приведенном выше рисунке пространство символов - это {0, 1}, текущее состояние - A, а вход 1, затем следующее состояние - 100% B, вход 0 - C, а остальные состояния такие же. Просто и легко реализовать.