Я новичок в CFG,
Может ли кто-нибудь дать мне совет по созданию CFG, который генерирует какой-либо язык
Например
L = {am bn | m >= n}
Что я получил:
So -> a | aSo | aS1 | e
S1 -> b | bS1 | e
но я думаю, что эта область неверна, потому что есть вероятность, что количество b может быть больше, чем a.
L = {am bn | м >= п}.
Описание языка: am bn состоит из a, за которым следует b, где число из a больше или равно числу b.
несколько примеров строк: {^, a, aa, aab, aabb, aaaab, ab......}
Таким образом, всегда есть один a на один b, но возможны и дополнительные a. строка заражения может состоять только из a. Также обратите внимание, что ^ null является элементом языка, поскольку в ^ NumberOf(a) = NumberOf(b) = 0
Как написать грамматику, которая принимает язык, образованный строками am bn?
В грамматике должны быть такие правила, что если вы добавляете символ b, вы также добавляете символ a.
и это можно сделать с помощью чего-то вроде:
S --> aSb
Но это неполное, потому что нам нужно правило для генерации дополнительных as:
A --> aA | a
Объедините два продукционных правила в одну грамматику CFG.
S --> aSb | A
A --> aA | a
Таким образом, вы можете сгенерировать любую строку, состоящую из a, а также a и b в (am b п) узор.
Но в приведенной выше грамматике нет способа сгенерировать строку ^.
Итак, измените эту грамматику следующим образом:
S --> B | ^
B --> aBb | A
A --> aA | a
эта грамматика может генерировать {am bn | m >= n} язык.
Примечание: чтобы сгенерировать пустую строку ^, я добавил дополнительный первый шаг в грамматике, добавив S--> B | ^, поэтому вы можете либо добавить ^, либо свою строку символов a и b. (теперь B играет роль S из предыдущей грамматики, чтобы создать равное количество a и b)
Изменить: Спасибо @Andy Hayden
Вы также можете написать эквивалентную грамматику для того же языка {am bn | м >= п}:
S --> aSb | A
A --> aA | ^
обратите внимание: здесь A --> aA | ^ может генерировать ноль или любое количество a. И это должно быть предпочтительнее моей грамматики, поскольку она генерирует меньшее дерево синтаксического анализа для той же строки.
(меньшее по высоте предпочтительнее из-за эффективного синтаксического анализа)
Следующие советы могут быть полезны при написании грамматики формального языка:
- Вы должны четко понимать язык, что он описывает (значение/шаблон).
- Вы можете запомнить решения некоторых основных проблем (идея в том, что вы можете написать новые грамматики).
- Вы можете написать правила для основных языков, таких как я написал для RE в этом примере написать Right-Linear-Grammmar. Правила помогут вам написать Грамматика для новых языков.
- Другой подход заключается в том, чтобы сначала нарисовать автоматы, а затем преобразовать автоматы в грамматику. У нас есть предопределенные методы написания грамматики из автоматов любого класса формального языка.
- Подобно хорошему программисту, который учится, читая чужой код, точно так же можно научиться писать грамматики для формальных языков.
Кроме того, написанная вами грамматика неверна.
S --> aSb | A, A --> aA | ^, таким образом, это не особый случай (и я думаю, что это более интуитивно понятно).
- person Andy Hayden; 24.04.2013
вы хотите создать грамматику для следующего языка
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
Наименьшие переменные: S -> a S b | а С | е
с меньшим количеством переменных:
S -> a S b | a S | a b | e
