Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Контекстно-свободная грамматика == Для того, чтобы определить контекстно-свободную грам…»)
 
Строка 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] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.

Формулировка задачи.

Задача вывода в контекстно-свободной грамматике состоит в поиске алгоритма, проверяющего, можно ли вывести данное слово в этой КС-грамматике.