Войти
В теории формального языка грамматика - это без контракта (или монотонный ), если все его продукционные правила имеют форму α → β, где α и β - строки из нетерминальных и конечных символов, а длина α меньше или равно β, | α | ≤ | β |, то есть β не короче α. Грамматика по существу не сокращает, если может быть одно исключение, а именно правило S → ε, где S - начальный символ , а ε - пустая строка, и, кроме того, S никогда не встречается в правая часть любого правила.
Ни одно из правил грамматики без контрактов не уменьшает длину перезаписываемой строки. Если каждое правило даже должным образом увеличивает длину, грамматика называется растущей контекстно-зависимой грамматикой.
Хомский (1963) назвал несдерживающуюся грамматику грамматикой типа 1 ; в той же работе он назвал контекстно-зависимую грамматику «грамматикой типа 2» и доказал, что эти две слабо эквивалентны (контекстно-независимые грамматики были обозначены как «тип 4 " в этой работе). Схема нумерации типов в этой работе Хомского 1963 года не совпадает с более ранней, известной сегодня как иерархия Хомского, потому что он пытался подчеркнуть различие между слабой [порождающей] и сильной [структурной] эквивалентностью; в своей работе 1959 года он использовал «грамматику типа 1» для обозначения контекстно-зависимой грамматики и «тип 2» для контекстно-свободной.
| S | → | abc |
| S | → | aSBc |
| cB | → | Bc |
| bB | → | bb |
Эта грамматика с начальным символом S генерирует язык {abc: n ≥ 1}, который не является контекстно-свободным из-за леммы перекачки.
Контекст -чувствительная грамматика для того же языка показана ниже.
Каждая неконтрактная грамматика (N, Σ, P, S) может быть преобразована в контекст- чувствительная грамматика (N ', Σ, P', S) следующим образом:
| X1 | X2 | ... | Xm-1 | Xm | → | Z1 | X2 | ... | Xм-1 | Xm | ||||||
| Z1 | X2 | ... | Xм-1 | Xm | → | Z1 | Z2 | ... | Xм-1 | Xm | ||||||
| : | ||||||||||||||||
| Z1 | Z2 | ... | Xм-1 | Xm | → | Z1 | Z2 | ... | Zм -1 | Xm | ||||||
| Z1 | Z2 | ... | Zм-1 | Xm | → | Z1 | Z2 | ... | Zм-1 | Zm | Yм + 1 | ... | Yn | |||
| Z1 | Z2 | ... | Zм-1 | Zm | Yм + 1 | ... | Yn | → | Y1 | Z2 | ... | Zм-1 | Zm | Yм + 1 | ... | Yn |
| Y1 | Z2 | ... | Zм-1 | Zm | Yм + 1 | ... | Yn | → | Y1 | Y2 | ... | Zм-1 | Zm | Yм + 1 | ... | Yn |
| : | ||||||||||||||||
| Y1 | Y2 | ... | Zм-1 | Zm | Yм +1 | ... | Yn | → | Y1 | Y2 | ... | Yм-1 | Zm | Yм + 1 | ... | Yn |
| Y1 | Y2 | ... | Yм-1 | Zm | Yм + 1 | ... | Yn | → | Y1 | Y2 | ... | Ym-1 | Ym | Ym + 1 | ... | Yn |
Например, выше грамматика несогласованности для {abc | n ≥ 1} приводит к следующей контекстно-зависимой грамматике (с начальным символом S) для того же языка:
| [a] | → | a | из шага 1 | ||||
| [b] | → | b | из шага 1 | ||||
| [c] | → | c | из шага 1 | ||||
| S | → | [apting | [bhibited | [c] | из шага 2, без изменений | ||
| S | → | [a] | S | B | [c] | с шага 2, без изменений | |
| с шага 2, дополнительно измененный ниже | |||||||
| [c] | B | → | Z1 | B | измененный сверху на шаге 3 | ||
| Z1 | B | → | Z1 | Z2 | изменено сверху на этапе 3 | ||
| Z1 | Z2 | → | B | Z2 | изменено сверху на этапе 3 | ||
| B | Z2 | → | B | [c] | изменено сверху на этапе 3 | ||
| из шага 2, дополнительно изменено ниже | |||||||
| [b] | B | → | Z3 | B | изменено сверху на этапе 3 | ||
| Z3 | B | → | Z3 | Z4 | изменено сверху на этапе 3 | ||
| Z3 | Z4 | → | [b] | Z4 | изменено сверху на этапе 3 | ||
| [b ] | Z4 | → | [b ] | [b] | изменено сверху на шаге 3 |
Аналогичным образом существует простая процедура для приведение любой неконтролируемой грамматики в нормальную форму Курода. И наоборот, каждая контекстно-зависимая грамматика и каждая грамматика нормальной формы Куроды тривиально также является несжимающей грамматикой. Следовательно, неконтактные грамматики, грамматики в нормальной форме Курода и контекстно-зависимые грамматики обладают одинаковой выразительной силой. Чтобы быть точным, неконтрактные грамматики описывают в точности контекстно-зависимые языки, которые не включают пустую строку, в то время как практически несогласованные грамматики описывают в точности набор контекстно-зависимых языков.
