49
правок
Изменения
Новая страница: «== Контекстно-свободная грамматика == Для того, чтобы определить контекстно-свободную грам…»
== Контекстно-свободная грамматика ==
Для того, чтобы определить контекстно-свободную грамматику, необходимо:
1) Задать конечное множество A - алфавит; его
элементы называют символами, а конечные последовательности симво-
лов называют словами (в данном алфавите);
2) Разделить все символы алфавита A на две группы: терми-
нальные ("окончательные") и нетерминальные ("промежуточные");
3) Выбрать один из нетерминальных символов, который будет считаться начальным;
4) Указать конечное число правил грамматики вида
K -> X
где K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов.
Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.
== Формулировка задачи. ==
Задача вывода в контекстно-свободной грамматике состоит в поиске алгоритма, проверяющего, можно ли вывести данное слово в этой КС-грамматике.
Для того, чтобы определить контекстно-свободную грамматику, необходимо:
1) Задать конечное множество A - алфавит; его
элементы называют символами, а конечные последовательности симво-
лов называют словами (в данном алфавите);
2) Разделить все символы алфавита A на две группы: терми-
нальные ("окончательные") и нетерминальные ("промежуточные");
3) Выбрать один из нетерминальных символов, который будет считаться начальным;
4) Указать конечное число правил грамматики вида
K -> X
где K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов.
Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.
== Формулировка задачи. ==
Задача вывода в контекстно-свободной грамматике состоит в поиске алгоритма, проверяющего, можно ли вывести данное слово в этой КС-грамматике.
