ТМВ-2020-Лекция-05.05.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Эквивалентность МТ и грамматик общего вида.

Эквивалентность МТ и грамматик общего вида

\(G\) - грамматика

\(\alpha \vdash^G \beta \Leftrightarrow \exists s_1 \vdash^G s_2 \vdash^G ... \vdash^G s_k \vdash^G \beta\)

Ассоциативное исчисление

{(\(\alpha,\beta\)) | \(\alpha \vdash^{G^*} \beta\)}\(=A\)

( МТ эквивалентна \(AU\) ) \(\Leftrightarrow\) ((\(\alpha,\beta\))\(\in A \Leftrightarrow МТ(\alpha) = \beta\))

То есть:

\(МТ(\alpha)=\beta \Leftrightarrow ([\alpha],\beta) \in A\)

\(AU\) по МТ

AU по МТ.png

\([PSQ]\)

Начальное состояние МТ \([S_0 \: Q]\)

Начинаем со строки \([' \: Q]\), плюс правило \([' \rightarrow [S_0\)

\(\Sigma_G = \Sigma_{МТ} \cup S_{МТ} \cup\) {\(_,[.]\)} - алфавит грамматики

\(a,s \rightarrow s',b,H \quad \quad \quad sa \rightarrow s'b\)

\(a,s \rightarrow s',b,L \quad \quad \quad \alpha sa \rightarrow s \alpha a, \forall \alpha \in \Sigma_{МТ}\)

\(a,s \rightarrow s',b,R \quad \quad \quad sa \rightarrow as\)

\(a,s \rightarrow s',b,L \quad \quad \quad [sa \rightarrow [s'_b\)

\(\lambda,s \rightarrow s',b,L \quad \quad \quad s] \rightarrow bs']\)

\(\lambda,s \rightarrow s',b,H \quad \quad \quad s] \rightarrow s'b]\)

\(\lambda,s \rightarrow s',b,R \quad \quad \quad \alpha s] \rightarrow s'\alpha ] \forall \alpha \in \Sigma_{МТ}\)

\([s] \rightarrow [s_b]\)

[PSt\(Q\)] - состояние, соответствующее терминальному состоянию МТ.

\(s \rightarrow ▲ \quad \quad \quad \quad \quad \quad \quad ►\alpha \rightarrow \alpha ►\forall \alpha \in \Sigma_{МТ}\)

\(\alpha ▲\rightarrow ▲ \forall \alpha \in \Sigma_{МТ} \quad \quad ►] \rightarrow \lambda\)

\([▲ \rightarrow ►\)

\(\Rightarrow Q \in \Sigma_{МТ}^*\)

\(N_G = \Sigma_G \ T_G\)

\(T_G = \Sigma_{МТ}\)

Полезная статья по курсу

https://habr.com/ru/post/491538/