Порождающие грамматики Хомского

[platerx]

Спасибо за статью!
Стоит добавить что грамматика 3-го типа так-же называется регулярной грамматикой. И одним из способов описания регулярной грамматики являются регулярные выражения.

[leotsarev]

S --> aA, A --> +aA, A --> +a
А нельзя проще:
S --> A, A --> a, A --> A+a
Или я чего-то не понял?

[humbug]

Такая грамматика подойдёт для aaa+a

[leotsarev]

Почему?
У меня не получается.
Как такая грамматика порождает aa хотя бы?

[humbug]

Я ошибся =)

[winger]

Тогда уж S --> a+A, A --> a, A --> A+a
Иначе будет порождаться строка «a».

[leotsarev]

Принято.

[humbug]

Не пойдёт. Левая рекурсия

[humbug]

(facepalm), не читайте.

[silvansky]

Ох, живо напомнило студенческие годы…

[raol]

Отличная статья, спасибо.
Еще, мне кажется, стоит написать про нормальную форму Хомского, и приведение к ней грамматик из ненормальной формы. То есть, когда у нас есть NT -> NT1 NT2 NT3 — ненормальная, а нам надо NT -> NT1* NT2*

[Amet13]

Еще раз спасибо за статью!
Очень интересно было увидеть на примере доказательство того, что язык, порождаемый циклической грамматикой, бесконечен.

[arheo_pterix]

Есть более наглядный пример)))

Стихотворение "Вот дом, который построил Джек" и естественно recursion