Разрешимые проблемы для а-грамматик

Теорема:

Если L– А-язык, иZLимеет длину,числа состояний детерминированного автомата, тоZ=WXY, гдеX1иWXⁱYLдля всехi0.

Доказательство: Пусть есть некоторый А-язык, и автомат M_L, порождающий этот язык.

Q-{q₀,_.q₁,q₂,…q_n-1} – множество состояний автоматаM_L,n- число состояний автомата,q_{0 –}начальное состояние автомата.

F(q₀,Z)K т.к. ZL. Zn , поэтому q_jQ , что Z=WXY, X 1, F(q₀,W)= q_j, F(q_j,X )= q_j, F(q_j, Y)K. Но тогда F(q₀,W XⁱY)K для всех i0, что требовалось доказать.

Теорема:

Проблема не пустоты для А-грамматик разрешима, т.е, если задана А-грамматика G, то существует алгоритм, позволяющий ответить на вопрос:L(G)=?

Например, Из предыдущей теоремы, если L(G), то существует цепочка длины<n, гдеn– число состояний детерминированного автомата (хотя это и не оптимальное решение).

Теорема:

Проблема равносильности А-грамматик разрешима. т.е., если G₁иG₂ – А-грамматики, то существует алгоритм, позволяющий определить,L(G₁)=L(G₂)?

Док-во: В случае равенства языков минимизированные детерминированные автоматы, построенные по этим грамматикам, будут совпадать с точностью до обозначений состояний.

Теорема:

Проблема конечности языка, порождаемого А-грамматикой, разрешима.

Обозначим множество состояний, достижимых из состояния A_i =H(A_i). Тогда, если

 A_i, такое, чтоA_iH(q₀)&A_iH(A_i)&A_jH(A_i)&A_jK, то язык, порождаемый автоматом, бесконечен.

Интересно отметить, что подобная теорема существует для КС-грамматик:

7. Нотации для задания кс-грамматик.

1. Математическая нотация (которую рассматривали до сих пор) – чистый синтаксис.

2. БНФ (Бекусова нормальная форма, или форма Бекуса — Наура) есть способ записи грамматики, который широко ис­пользуется для описания синтаксиса языков программирования. В БНФ

   1. нетерминальные символы записываются как имена, за­ключенные в угловые скобки < > .

   2. Знак записывается как ::=(читается "заменяется на").

   3. Альтернативы замены, соот­ветствующие одному и тому же нетерминалу в левой части, от­деляются друг от друга вертикальной чертой (читается "или").

   4.  не обозначается, для того, чтобы не пропыстить эту альтернативуЮ она обычно записывается первой в конструкции выбора.

Используя БНФ, описание идентификатора как произвольной по­следовательности букв и цифр, начинающейся с буквы, можно, например, записать:

<идентификатор> ::=<буква> | <буква> <продолжение>

<продолжение> ::= < символ> | < символ> <продолжение>

<символ> ::= < буква> | <цифра>

<буква> :: =А | В | С|….|Z

<цифра> ::=0 | 1 | ... | 9

Или:

<идентификатор> ::= <буква> <продолжение>

<продолжение> ::= | < символ> <продолжение>

<символ> ::= < буква> | <цифра>

<буква> :: =А | В | С|….|Z

<цифра> ::=0 | 1 | ... | 9

При записи в виде грамматики G₁₃семантику увидеть сложнее(запись полностью соответствует последнему варианту БНФ):

S  A B

B  A B 

ACD

CА | В | С|….|Z

D0 | 1 | ... | 9

Нетерминал БНФ может интерпретироваться как язык, который выводится, если рассматривать данный символ как начальный символ грамматики. БНФ может использоваться для описания синтаксиса любого языка, не только искусственного, например:

<Существительное > :: =<основа > <окончание>

<окончание > ::=окончание множественного числаокончание единственного числа…

Или:

формула исчисления высказываний::=элементарная формула(формула исчисления высказыванийбинарная операцияформула исчисления высказываний)(отрицание

формула исчисления высказываний)

элементарная формула::=константапропозициональная переменная

константа::= 01

пропозициональная переменная ::=ab…z

отрицание::=N

бинарная операция::=

3. Часто применяется так называемая расширенная БНФ -РБНФ в которой используются также метасимволы (,); [,]; {,}. Ведение метасимволов позволяет сделать запись более лаконичной . Синтаксис РБНФ следующий

   1. Нетерминалы записываются как последовательность символов.

   2. Терминалы( последовательности символов) заключаются в кавычки.

   3. Знак , используемый в математической записи грамматик, обозначается как =.

   4. Альтернативы, как и в математической записи грамматик, разделяются знаком .

   5. Конструкция, заключенная в ,, является необязательной.

   6. Конструкция, заключенная в ,может повторяться произвольное число раз, от 0 (эквивалент * в регулярных выражениях).

   7. ( ) служат для факторизации, т.е. конструкция может быть представлена в виде (). Это позволяет использовать конструкцию выбора на более глубоком уровне.

Например, идентификатор в РБНФ будет описан как:

Идентификатор = буква буквацифра

буква = 'А’ | ‘В’ | ‘С’ |….| ‘Z’

цифра = ‘0’ | ‘1’ | ... | ‘9’

Существительное описывается как

существительное = основа ( окончание единственного числаокончание множественного числа)

Фактически, в правой части правил в РБНФ записывается некоторое регулярное выражение, в котором могут использоваться нетерминалы (т.е. расширение возможностей относительно выразительной мощности обычных регулярных выражений, т.к. обычные регулярные выражения позволяют описывать А-языки, а РБНФ – КС-языки.

4. Синтаксическая диаграмма. Синтаксическая диаграмма – графическая форма представления РБНФ. Для каждого нетерминала рисуется своя диаграмма. Приняты следующие обозначения:

   1. Нетерминалы заключаются в прямоугольники.

   2. Терминалы заключаются в овалы.

   3. Образы нетерминалов и терминалов соединяются линиями (со стрелками или без, мы будем использовать стрелки для указания направления движения) т.о., чтобы множество путей соответствовало множеству цепочек из терминалов и нетерминалов, задаваемому РБНФ - правилами, для которых строится диаграмма.

Диаграммы для конструкции выбора и итерации представлены на рис. 22, а и б, соответственно. Скругленный прямоугольник может быть заменен как прямоугольником (в случае нетерминала), так и овалом ( в случае терминала).

Набор диаграмм для идентификатора на рис. 23.

Буква

Цифра

Буква

Буква

….

А

B

Z

Идентификатор

….

1

0

2

Цифра

а

б

Рис.22

Рис.23

В большинстве случаев существует не единственная форма представления для одних и тех же объектов.

Легко показать, что выразительная мощность РБНФ и БНФ совпадает:

Условная запись РБНФ	Условная запись БНФ для данной РБНФ
А= (12)	<А> ::=<>< 1>< ><2>
А= [ ] 	<А> ::=<>< >< >
А= { } 	<А> ::= <B ><> <B> ::= <> < B>