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