mefrill Apr 24 2013 at 18:05

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

12 min

134K

Algorithms * Mathematics * Programming *

+47

Comments 13

platerx Apr 24 2013 at 19:42

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

leotsarev Apr 24 2013 at 19:59

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

humbug Apr 24 2013 at 21:58

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

leotsarev Apr 24 2013 at 22:02

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

humbug Apr 24 2013 at 22:11

Я ошибся =)

winger Apr 24 2013 at 21:59

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

leotsarev Apr 24 2013 at 22:02

Принято.

humbug Apr 24 2013 at 22:05

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

humbug Apr 24 2013 at 22:48

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

silvansky Apr 25 2013 at 08:02

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

raol Apr 25 2013 at 08:37

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

UFO landed and left these words here

arheo_pterix Nov 25 2023 at 16:05

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

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