Советы по созданию "Грамматики без контекста"
Я новичок в CFG,
Может кто-нибудь дать мне советы по созданию CFG, который генерирует какой-то язык
Например
L = {am bn | m >= n}
Что я получил это:
So -> a | aSo | aS1 | eS1 -> b | bS1 | e
но я думаю, что эта область не так, потому что есть вероятность того, что число b может быть больше, чем a "S.
4 ответа
Как написать CFG с примером a m b n
L = {a m b n | m> = n}.
Описание языка: a m b n состоит из a с последующим b где число a равны или больше, чем количество b,
некоторые примеры строк: {^, a, aa, aab, aabb, aaaab, ab......}
Так что всегда есть один a для одного b но дополнительно a возможны зараженная строка может состоять из a только. Также обратите внимание ^ нуль является членом языка, потому что в ^NumberOf(a) = NumberOf(b) = 0
Как написать грамматику, которая принимает язык, образованный строками a m b n?
В грамматике должны быть такие правила, что если вы добавите b символ вы также добавляете a условное обозначение.
и это можно сделать с помощью чего-то вроде:
S --> aSb
Но это неполно, потому что нам нужно правило, чтобы генерировать дополнительные a s:
A --> aA | a
Объедините два правила производства в одну грамматику CFG.
S --> aSb | A
A --> aA | a
Таким образом, вы можете генерировать любую строку, состоящую из a также a а также b в (A m B N) шаблон.
Но в вышеприведенной грамматике нет способа генерировать ^ строка.
Итак, измените эту грамматику следующим образом:
S --> B | ^
B --> aBb | A
A --> aA | a
эта грамматика может генерировать {a m b n | m> = n} язык.
Примечание: для генерации ^ пустая строка, я добавил дополнительный первый шаг в грамматике, добавив S--> B | ^, Так что вы можете добавить ^ или ваша строка символов a а также b, (сейчас B играет роль S из предыдущей грамматики, чтобы генерировать равные числа a а также b)
Редактировать: благодаря @ Энди Хейден
Вы также можете написать эквивалентную грамматику для того же языка {a m b n | m> = n}:
S --> aSb | A
A --> aA | ^
обратите внимание: здесь A --> aA | ^ может генерировать ноль или любое количество a, И это должно быть предпочтительнее моей грамматики, потому что она генерирует меньшее дерево разбора для той же строки.
(меньше по высоте предпочтительнее из-за эффективного разбора)
Следующие советы могут быть полезны при написании грамматики для формального языка:
- Вы должны четко понимать язык, который он описывает (значение / образец).
- Вы можете вспомнить решения для некоторых основных задач (идея заключается в том, что вы можете писать новые грамматики).
- Вы можете написать правила для основных языков, как я написал для RE в этом примере, чтобы написать Right-Linear-Grammmar. Правила помогут вам написать грамматику для новых языков.
- Один другой подход состоит в том, чтобы сначала нарисовать автоматы, а затем преобразовать автоматы в грамматику. У нас есть предопределенные методы для написания грамматики из автоматов из любого класса формального языка.
- Как Хороший Программист, который учится, читая код других, так же можно научиться писать грамматики для формальных языков.
Также написанная вами грамматика неверна.
Вы хотите создать грамматику для следующего языка
L= {an bm | m>=n }
это означает, что число "b" должно быть больше или равно числу "a", или вы можете сказать, что для каждого "b" может быть не более одного "a". не наоборот.
вот грамматика для этого языка
S-> aSb | Sb | b | ab
в этой грамматике для каждого "а" есть один "б". но b можно сгенерировать, не генерируя никаких "a".
Вы также можете попробовать эти языки:
L1= {an bm | m > n }
L2= {an bm | m >= 2n }
L3= {an bm | 2m >= n }
L4= {an bm | m != n }
Я даю грамматику для каждого языка.
для L1
S-> aSb | Sb | b
для L2
S-> aSbb | Sb | abb
для L3
S-> AASb | Sb | aab | ab | b
для L4
S-> S1 | S2
S1-> aS1b | S1b | b
S2-> aS2b | aS2 | a