Контекстная грамматика для множества {a, b} со спецификацией length / amt? - PullRequest
Новая
       2

Контекстная грамматика для множества {a, b} со спецификацией length / amt?

0 голосов
/ 08 июня 2018

Это вопрос практического экзамена, поэтому, пожалуйста, объясните ответы, а также дайте советы для размышления о подобных проблемахПоэтому у меня есть вопрос:

Создать контекстно-свободную грамматику для языка, который принимает строки в алфавите {a, b}, где число a делится на 3 или длина x делитсяна 3 или оба .... где x = входная строка.

Я много борюсь с тем, как я должен начать проблему.

Я понимаю, чтограмматика для приема строк из алфавита {a, b}, которая делится на 3, может выглядеть следующим образом: 

0 -> a1 | b1
1 -> a2 | b2 
2 -> a | b | a0 | b0

Ниже я до сих пор пытаюсь отследить как общую длину xи количество а в х, для любой комбинации а и б: 

0 -> a1 | b1
1 -> a2 | b3
2 -> a | a0 | b1
3 -> a | b | a2 | b4
4 -> a1 | b5
5 -> b | b1 | a2

Выше явно неверно, но мне нужна помощь.Вот пример строки, которая должна пройти: 

ababab
abaa
abbabb

1 Ответ

0 голосов
/ 28 июня 2019

Из моего опыта и обучения лучше всего:

Рекурсивно строить грамматику

При построении грамматики этого типа (определенного числа терминалов) лучше всего делать это рекурсивно.Сначала вы предполагаете, что вашим начальным символом является желаемая строка.Затем вы разбиваете его на подстроки, каждая из которых все еще соответствует вашим правилам, пока не останутся только терминалы.

Вы подошли к проблеме аддитивно, построив строку с нуля и попытавшись подсчитать, сколько терминалов у вас есть, какой контекстК сожалению, свободные грамматики не могут (они могут, но только для конечных строк).

Таким образом, первое правило будет 

S -> 3

где 

S...starting symbol
3..."multiple of three"

"Несколькоиз трех "может быть либо строкой с 3 a, либо строкой длиной 3. 

3 -> A | L

, где 

A...string with 3 a's 
L...string with length of 3

Чтобы иметь возможность построить строку любой длины, мы можем сложить вместелюбые строки, соответствующие одному и тому же «правилу трех». 

A -> AA
L -> LL

Теперь - строки длины 3 просты.

L -> aM | bM
M -> aN | bN 
N -> a | b

3a строка - это просто строка из трех a с любым количеством b, разбросанных между тремя a и вокруг них. 

A -> bA | aB  
B -> bB | aC
C -> bC | a | aD
D -> bD | b

Строка 3a строится слева направо.Каждое правило может генерировать любое количество b, пока оно не закроет их a.Последнее правило может производить любое число b с правой стороны.

Все вместе: 

S -> 3

3 -> A | L 
L -> LL | aM | bM
M -> aN | bN 
N -> a | b
A -> AA | bA | aB  
B -> bB | aC
C -> bC | a | aD
D -> bD | b

Замечания

  1. Рекурсивно строить грамматику
  2. Построить грамматику из маленьких единиц
...