Грамматика, которая принимает пустое множество по правилу S-> S - PullRequest
Новая
       72

Грамматика, которая принимает пустое множество по правилу S-> S

13 голосов
/ 26 сентября 2011

Это была проблема с домашним заданием, на которую, как я знаю, я ответил неправильно.Я дал: 

S -> ''

, что означает, что S дает пустую строку.Я знаю, что пустой набор и пустая строка не совпадают.По словам моего профессора, ответ таков: 

S -> S

Теперь этот ответ кажется мне странным:

  1. Он никогда не закончится.
  2. Это не такЭто не столько язык, сколько его отсутствие.

Я понимаю, с чисто математической точки зрения, я не собираюсь никуда переходить с номером два.Однако требуется ли прекращение языка?Иметь язык, который МОЖЕТ продолжаться вечно, звучит хорошо, но тот, который никогда не закончится, звучит неправильно, поэтому я подумал, что я спрошу, знает ли кто-нибудь, является ли это языковым требованием или нет.

1 Ответ

12 голосов
/ 26 сентября 2011

Со страницы Формальной грамматики Википедии :

язык G, обозначаемый как L (G), определяется как все те предложения, которые могут быть получены за конечное число шагов из начального символа S.

Начиная с S, применение правила производства один раз к S дает S. Применение правила дважды дает S. По индукции, применение правила для любого конечного числа по-прежнему дает S. Поскольку никакие предложения не могут быть получены за конечное число шагов, язык пустой, значит, ваш профессор прав.

Альтернативные способы определения грамматики, которая принимает пустой набор: L(G) = {} (язык пуст) или P = {} (набор правил производства пуст).

...