Грамматика

  • 04 окт. 2011 г.
  • 6904 Слова
1 Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где
VT - алфавит терминальных символов (терминалов),
VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,
P - конечное подмножество множества (VT ∪ VN)+ × (VT ∪ VN)*; элемент (α, β) множества P называется правилом вывода и записывается в виде α → β,
S - начальный символ (цель) грамматики, S ∈VN.

Для записи правил вывода с одинаковыми левыми частями
α → β1, α → β2, ..., α → βn
будем пользоваться сокращенной записью
α → β1 | β2 |...| βn.
Каждое βi , i= 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки α.

Пример грамматики:
G1 = ({0,1}, {A,S}, P, S),
где P состоит из правил
S → 0A1
0A → 00A1
A → (

2 Классификация грамматик
Правила порождающихграмматик позволяют осуществлять преобразования строк. Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.
Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений. Грамматики типа i, или контекстные грамматики -это грамматики, все правила которых имеют следующий вид: хАу — хфу, где A e VN, x, y, ф e (VN u VT)+.Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС- грамматики). Правила вывода для этих грамматик имеют следующий вид: А — ф, где А e Vn, ф e (Vn u Vt)*.
Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:
а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий вид: А — Аа | a, где А e VN;
б) праволинейные (праворекурсивные), правилавывода для которых имеют следующий вид: А — Аа | a.
Язык L называется языком типа i, если существует грамматика типа i, порождающая язык L

Операция итерации реализуется удалением циклов из начальных и заключительных состояний и объединения полученных состояний. Объединение начального и заключительного состояний означает, что построенный автомат допускает пустую цепочку. Однократный переход изначального в заключительное состояние исходного автомата соответствует допуску цепочек языка L. Поскольку эти состояния объединены, автомат допускает цепочки языков LL, LLL и т.д., т.е. он распознает язык ^}uLuL u . . . =L .
Операция произведения над L(A1) и L(A2) выполняется с помощью двух преобразований: а) удаляются циклы из начального состояния А2 и заключительного состояния А1; б) каждомузаключительному состоянию А1 ставим в соответствие свой экземпляр А2 и объединяем заключительные состояния А1 с начальным состоянием соответствующего экземпляра А2.
Объединение L(A1) и L(A2) строится с помощью удаления циклов в начальных состояниях А1 и А2 и объединения полученных начальных состояний.
Усеченная итерация может быть построена двумя способами:
а) L(Ai)+ = L(Ai)* L(Ai),
б) L(Ai)+ = L(Ai)L(Ai)*.
Рассмотрим дополнение L(A1) до £*. Пусть автомат А1 детерминированный, тогда любая цепочка x=a1a2 . . an распознается по единственному маршруту:
p0ai ^ pi pia2 ^ p2
pn-ian ^ pn, Pnе F.
Автомат не распознает только те цепочки, которые:
либо представляют собой начальную часть цепочки a1a2 . . aj, при чтении которой автомат переходит в состояние, не являющееся заключительным;
либо имеютвид y = a1a2 . . akbc1c2 . . cm (k < n), где начало цепочки a1a2 . . ak совпадает с началом цепочки xеL(А1), но за символом ak стоит такой символ Ь, что автомат А1 его прочитать не может.
Поэтому для того чтобы построить автомат, распознающий дополнение языка, необходимо:
а) все заключительные состояния сделать незаключительными, а незаключительные состояния - заключительными;
б) ввестидополнительное состояние, сделать его заключительным и из каждого состояния провести в это состояние такие дуги, каждая из которых соответствует символам алфавита, не читаемым в этом состоянии;
в) в построенном дополнительном состоянии построить петли для всех символов алфавита, чтобы обеспечить чтение произвольного окончания цепочки c1c2 . . cm.
Разность L(A1) и L(A2) строится...
tracking img