Разница между обычным языком и обычной грамматикой

Question

Моя книга дает похожие, но немного отличающиеся объяснения обычной грамматики и обычного языка.Я сомневаюсь, что это неправильно, обычный язык - это то же самое, что и обычная грамматика?Определение моей книги таково: грамматика регулярна, если все произведения V-> aW или V-> Wa с V, W нетерминальными или терминальными символами, «a» терминальный символ. W также может быть пустым или совпадатьВ.

Answer 1

Формальная грамматика - это набор правил, тогда как формальный язык - это набор строк.

Обычная грамматика - это формальная грамматика, которая описывает обычный язык.

Согласно Википедии :

[T] он оставил обычные грамматики, генерирующие ровно все обычные языки.Правильные регулярные грамматики описывают обратные стороны всех таких языков, то есть точно также регулярных языков.

Если допустимо смешивание левых и правых регулярных правил, у нас все еще есть линейная грамматика, ноне обязательно регулярный.

В приведенном выше лево-регулярные правила - это правила вида V->Wa (правосторонний, вида V->aW).

Answer 2

Обычные грамматики и обычные языки - это два разных термина:

1. A язык - это (возможно, бесконечный) набор допустимых последовательностей терминальных символов. грамматика определяет допустимые последовательности.

Один и тот же язык может быть представлен различным классом грамматик (регулярный, контекстно-свободный и т. Д.). A язык называется регулярным, если его можно представить с помощью обычной грамматики .С другой стороны, регулярная грамматика всегда определяет обычный язык.То, что вы опубликовали, это определение обычной грамматики.

См. этот пост в Википедии для получения дополнительной информации.