06.tex

\setcounter{section}{5}

\section{ПОЛІЗ, регулярні вирази, і автомати}

\subsection{Польський інверсний запис для регулярних виразів}

Польський інверсний запис (ПОЛІЗ) для регулярних виразів будується на основі початкового регулярного виразу на основі наступних правил:
\begin{enumerate}
	\item Порядок операндів в початковому виразі і в перетвореному виразі співпадають.
	\item Операції в перетвореному виразу йдуть з урахуванням пріоритету безпосередньо за операндами.
\end{enumerate}

Наприклад, ПОЛІЗ для виразу $(a^\star+b)^\star c$ має такий вигляд:
\begin{equation}
    a, \star, b, +, \star, c, \cdot
\end{equation}

В цьому прикладі в стандартному записі регулярного виразу бінарна операція конкатенація $\cdot$ природньо опущена, але в ПОЛІЗ потрібно завжди цю операцію явно вказувати. \medskip

Важливою характеристикою ПОЛІЗ є відсутність дужок в запису виразу, тобто його можна опрацьовувати лінійно.

\subsubsection{Алгоритм}

Для перетворення виразу в ПОЛІЗ необхідно з кожною операцією зв'я\-за\-ти деяке число, яке будемо називати ``пріоритет'' (0 --- найвищий пріоритет присвоїмо дужці \verb|'('|). Наведемо псевдокод алгоритму:
\begin{verbatim}
while lexem <- прочитати поточну лексему:
    if lexem is операнд:
        занести її в поле результату
	
    if lexem = '(':
        занести її в стек
	
    if lexem is код операції:
        while (пріоритет операції на вершині стека >= \
        	пріоритет поточної операції):
            елемент з вершини стека перенести в поле результату
        поточну лексему занести в стек
	
    if lexem = ')':
        while код операції на вершині стеку != '(':
            елемент з вершини стека перенести в поле результату
        дужку '(' зняти з вершини стека

всі елементи із стека перенести в поле результату
\end{verbatim}

\subsection{Інтерпретація ПОЛІЗ регулярного виразу}

Результат інтерпретації ПОЛІЗ --- це скінченний автомат $M$, який розпізнає (сприймає) множину ланцюжків, котрі позначає регулярний вираз.

\subsubsection{Алгоритм}

Наведемо псевдокод алгоритму:
\begin{verbatim}
while lexem <- прочитати поточну лексему:
    if lexem is операнд ai:
        M: L(M) = {ai\}
	
    if lexem = '+':
        M1, M2 <- автомати з вершини стеку
        M: L(M) = L(M1) \cup L(M2)
		
    if lexem = '\times':
        M1, M2 <- автомати з вершини стеку
        M: L(M) = L(M2) \times L(M1)

    if lexem = '\star':
        M1 <- автомат з вершини стеку
        M: L(M)= L(M1)^\star

    M занести в стек

вершину стека перенести в поле результату
\end{verbatim}

Якщо досягли кінця регулярного виразу, то на вершині стека знаходиться автомат $M$, який розпізнає множину слів (ланцюжків), які позначає регулярний вираз.

\subsection{Контрольні запитання}

\begin{enumerate}
	\item Що таке ПОЛІЗ?
	\item Чи можна в ПОЛІЗ опускати операції які природнім чином опускаються у класичному записі? % ні
	\item Яка основна характеристика ПОЛІЗ і яку обчислювальну перевагу вона пропонує? % відсутність дужок дозволяє (природнім чином) обчислювати вирази лінійно
	\item Сформулюйте алгоритм перетворення регулярного виразу у ПОЛІЗ та оцініть його складність.
	\item Що є результатом інтерпретації ПОЛІЗ регулярного виразу? % скінченний автомат який розпознає ту ж мову яку описує регулярний вираз
	\item Сформулюйте алгоритм інтерпретації ПОЛІЗ регулярного виразу.
	\item Оцініть складність попереднього алгоритму через складності операцій побудови автоматів.
	\item Для регулярного виразу $(a^\star + b)^\star \cdot c$ побудуйте скінчений автомат, який розпізнає множину ланцюжків, що позначаються цим виразом.
\end{enumerate}