Иерархия Хомского: определения

[Tookser]

Столкнулся с тем, что в разных пособиях определения грамматик 0, 1, 2 и 3 типов немного отличаются. Есть вариант определения, при котором эти множества грамматик (а также множества языков) не являются вложенными друг в друга, а это не очень красиво. В этом варианте мы определяем грамматику типа 1 как грамматику, в которой все правила имеют вид $\beta A \gamma\to\beta\alpha\gamma$, где$\beta$ и $\gamma$ - произвольные строки, $A$ - нетерминал, и $\alpha$ - непустая строка. Однако тогда все языки типа 1 не будут включать пустую строку. В то же время в грамматиках типа 2 и 3 разрешаются $\varepsilon$-правила, и тогда у нас будут грамматики типа 2 или 3, не являющиеся грамматиками типа 1.
Есть также вариант определения, при котором в грамматиках всех типов допускается $\varepsilon$ правило, но только вида $S \to\varepsilon$ (и при этом запрещается иметь в правой части правил $S$). Тогда вроде бы всё получается вложенно, и грамматики, и языки, но отсутствие возможности использовать произвольное $\varepsilon$-правило немного мешает.
Как лучше?

[Sonic86]

Tookser в сообщении #1131591 писал(а):

В этом варианте мы определяем грамматику типа 1 как грамматику, в которой все правила имеют вид $\beta A \gamma\to\beta\alpha\gamma$, где$\beta$ и $\gamma$ - произвольные строки, $A$ - нетерминал, и $\alpha$ - непустая строка. Однако тогда все языки типа 1 не будут включать пустую строку.

А почему это?
Разве правило $A\to\varepsilon$ не имеет вида $\beta A \gamma\to\beta\alpha\gamma$?

[Tookser]

Sonic86, $\alpha$ - непустая строка.

[Sonic86]

Tookser в сообщении #1131618 писал(а):

Sonic86, $\alpha$ - непустая строка.

С чего вдруг?

Чего-то я не могу определение найти.

[Tookser]

Sonic86 в сообщении #1131619 писал(а):

Tookser в сообщении #1131618 писал(а):

Sonic86, $\alpha$ - непустая строка.

С чего вдруг?

Везде, где я видел определение грамматики типа 1, это указывалось.

[Sonic86]

Tookser в сообщении #1131620 писал(а):

Везде, где я видел определение грамматики типа 1, это указывалось.

Скажите книжку. Я просто удивлен. Скорее всего это несущественная мелочь.
Нашел только тут: http://neerc.ifmo.ru/wiki/index.php?tit ... 0%B8%D0%BA
но это не книжка.

[Tookser]

Допустим, Волкова, Формальные грамматики и языки. Элементы теории трансляции. Второе издание. Или Пентус, Теория формальных языков.

[Sonic86]

Да, действительно. Странно.
Конечно, чтобы хорошо понять вопрос, надо откопать все теоремы о КЗ-грамматиках, где этот пункт существенен.
А формально можно просто определить на каждый тип грамматики по 2 подтипа - $\varepsilon$-порождающие и непорождающие. Соответственно будет 2 иерархии вида $3\subset 2\subset 1\subset 0$.
Далее для каждой $\varepsilon$-непорождающей грамматики легко строится $\varepsilon$-порождающая добавлением одного нового нетерминала $S'$ с объявлением его начальным нетерминалом с 2-я новыми правилами $S'\to \varepsilon$ и $S'\to S$. А для каждой $\varepsilon$-порождающей грамматики нетрудно построить $\varepsilon$-непорождающую с помощью замены правила $\alpha A\beta \to \alpha \gamma\beta$ на 2 правила $\alpha A\beta \to \alpha \gamma\beta$ с $\gamma \neq \lambda$ и $\alpha A\beta \to \alpha \beta$, если такое возможно, и выкидыванием всех $\varepsilon$-продукций. Т.е. они эквивалентны с точностью до $\varepsilon$ и дальше можно выбрать нужный вариант и рассуждать.

Т.е. я думаю, что это просто некритично. Хотя я на самом деле не специалист

[Tookser]

Может быть, проще отказаться от вложенности типов грамматик, добавив возможность правила $S \to\varepsilon$ в грамматике типа 1 (и при этом запретить иметь в правой части правил $S$). Тогда грамматики не вложены, но языки будут вложены. В английской вики вроде так (почти) сделано.
UPD:

(Оффтоп)

В статье про иерархию Хомского сделано как-то не так, в этой статье вроде всё так (эпсилон правила допущены в контекстно-свободных грамматиках), только ничего не сказано про регулярные грамматики, в них можно тоже допустить $\varepsilon$-правила.

[whitefox]

Tookser в сообщении #1131591 писал(а):

В этом варианте мы определяем грамматику типа 1 как грамматику, в которой все правила имеют вид $\beta A \gamma\to\beta\alpha\gamma$, где$\beta$ и $\gamma$ - произвольные строки, $A$ - нетерминал, и $\alpha$ - непустая строка. Однако тогда все языки типа 1 не будут включать пустую строку.

Если у вас есть КЗ грамматика $G,$ то язык $L(G)\cup\{\varepsilon\}$ обычно считается КЗ. Для этого к грамматике $G$ добавляется нетерминал $S'$ и продукция $S'\rightarrow\varepsilon\mid S,$ где $S$ стартовый символ грамматики $G.$ В новой грамматике $G'$ стартовым символом полагают $S'.$

А чтобы грамматики, подобные $G',$ тоже считались КЗ, определение КЗ грамматики добавляют правилом: эпсилон продукция допустима только со стартовым символом при условии, что стартовый символ не входит в правую часть ни одной продукции.

-- 15 июн 2016, 11:11 --

Пардон, вы об этом уже написали в последнем посте.