ВУЗ:
Составители:
В качестве примера покажем алгоритмическую разрешимость проблемы пустоты и
проблемы принадлежности для А-языков, используя для этого модель конечного
автомата.
Проблемы пустоты А-языка можно сформулировать следующим образом: задан
КА А, допускающий язык. Пустой ли этот язык? Приведем конструктивное
доказательство разрешимости проблемы пустоты. Пусть дан КА
{
}
'),,(,,,
0
QxqIqQVА
x
= ,
где
x
V - входной алфавит,
Q
- алфавит состояний, Qq
∈
0
- начальное состояние,
),( xqI
-
функция переходов, а
QQ ≡'- множество заключительных состояний.
Если язык )(
AL =Ø, то будем говорить «да» (язык пуст, если ) )(AL ≠Ø, то будем
говорить «нет» (язык не пуст). Алгоритм решения проблемы пустоты заключается в
следующем. Вычисляется множество состояний, достижимых из
0
q . Если это множество
не содержит ни одного состояния
'Q
, то можем сказать «да» (язык пуст) в противном
случае говорим «нет» (язык не пуст). Заметим, что состояние
Qq
jk
∈
называется
достижимым из
Qq ∈
0
, если при подаче на выход автомата некоторого входного слова
ikii
xxx K
21
=
α
на графе автомата существует последовательность
jkikjiji
qxqxqxq K
22110
,
которая начинается в начальном состоянии
0
q и заканчивается в состоянии
jk
q .
Проблему принадлежности можно сформулировать следующим образом: задан КА
А, допускающий язык
)(AL
и слово
α
; принадлежит ли
α
языку
)(AL
? Доказательство
разрешимости этой проблемы также проведем конструктивно. Пусть задан тот же автомат
{
}
'),,(,,,
0
QxqIqQVА
x
= и слово
*
x
V∈
α
. Будем говорить «да», если слово )(AL∈
α
, и
«нет», если
)(AL∉
α
. Алгоритм решения проблемы принадлежности состояния
),(,),,(),.(
1212101 nnn
xqIqxqIqxqIq
−
=== K . Если 'Qq
n
∈
, то говорим «да», если 'Qq
n
∉
, то
говорим «нет».
В заключение раздела отметим, что нами были рассмотрены не только конечные
автоматы, которые можно использовать для распознавания правильности конструкций
языка, но и конечные автоматы с выходами, которые являются преобразователями слов
одного алфавита в слова другого алфавита или физически реализуемыми трансляторами
А-языков. По аналогии с односторонними ленточными
преобразователями можно ввести
выходной алфавит и соответствующую ему выходную ленту для других типов автоматов.
В этом случае получим преобразователи соответствующих типов языков.
ЗАКЛЮЧЕНИЕ
Мы рассмотрели основные понятия теории формальных языков и показали их
взаимосвязь с такими понятиями, как алгоритм, машина Тьюринга, формальная система.
Мы выяснили, что грамматики Хомского являются хорошей моделью языков
программирования. Однако все сказанное относится исключительно к синтаксису
формальных языков (точнее говоря, языков Хомского). Фактически мы не касались одной
важной их
составляющей – семантики. Мало было сказано и об одном из важнейших
разделов математического обеспечения – разработке трансляторов.
Семантика языка- правила, объясняющие смысл его синтаксически правильных
конструкций. Семантику программ необходимо знать, чтобы знать, как исполнять данную
программу на ЭВМ. Семантические правила можно записать на некотором формальном
(семантическом) языке и оформить в виде семантических
подпрограмм. С каждой
синтаксической конструкцией тогда можно связать свою семантическую подпрограмму.
Основная трудность, возникающая при таком подходе- сложность формального задания
всех семантических правил языка. Это обстоятельство, так же как и сложность
