mefrill Apr 24 2013 at 22:05

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

12 min

120K

Programming*Algorithms*Mathematics*

Tutorial

+48

Comments 13

platerx Apr 24 2013 at 23:42

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

leotsarev Apr 24 2013 at 23:59

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

humbug Apr 25 2013 at 01:58

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

leotsarev Apr 25 2013 at 02:02

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

humbug Apr 25 2013 at 02:11

Я ошибся =)

winger Apr 25 2013 at 01:59

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

leotsarev Apr 25 2013 at 02:02

Принято.

humbug Apr 25 2013 at 02:05

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

humbug Apr 25 2013 at 02:48

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

silvansky Apr 25 2013 at 12:02

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

raol Apr 25 2013 at 12:37

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

Amet13 May 16 2013 at 23:06

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

arheo_pterix Nov 25 2023 at 19:05

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

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

Show the best of all time