APR SEP FEB 18 2006 2008 2012 14 captures 30 Mar 05 - 5 Feb 12

Close Help

В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.

Основные понятия и определения

Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ ε.

Более формально цепочка символов в алфавите V определяется следующим образом:

(1)    ε - цепочка в алфавите V;

(2)    если α - цепочка в алфавите V и a - символ этого алфавита, то αa - цепочка в алфавите V;

(3)    β - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Определение: если α и β - цепочки, то цепочка αβ называется конкатенацией (или сцеплением) цепочек α и β.

Например, если α = ab и β = cd, то αβ = abcd.

Для любой цепочки α всегда αε = εα = α.

Определение: обращением (или реверсом) цепочки α называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки α будем обозначать α^R.

Например, если α = abcdef, то α^R = fedcba.

Для пустой цепочки: ε = ε^R.

Определение: n-ой степенью цепочки α (будем обозначать αⁿ) называется конкатенация n цепочек α.

α⁰ = ε; αⁿ = αα^n-1 = α^n-1α.

Определение: длина цепочки - это число составляющих ее символов.

Например, если α = abcdefg, то длина α равна 7.

Длину цепочки α будем обозначать | α |. Длина ε равна 0.

Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

Определение: обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку ε.

Например, если V={0,1}, то V^* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.

Определение: обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку ε.

Следовательно, V^* = V⁺ ∪ {ε}.

Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.

Определение: декартовым произведением A × B множеств A и B называется множество {(a,b) | a ⊂ A, b ⊂ B}.

Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где

VT - алфавит терминальных символов (терминалов),

VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,

P - конечное подмножество множества (VT ∪ VN)⁺ × (VT ∪ VN)^*; элемент (α, β) множества P называется правилом вывода и записывается в виде α → β,

S - начальный символ (цель) грамматики, S ⊂ VN.

Для записи правил вывода с одинаковыми левыми частями

α → β₁ α → β₂ ... α → β_n

будем пользоваться сокращенной записью

α → β₁ | β₂ |...| β_n.

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

Пример грамматики:

G1 = ({0,1}, {A,S}, P, S),

где P состоит из правил

S → 0A1

0A → 00A1

A → ε

Определение: цепочка β ⊂ (VT ∪ VN)^* непосредственно выводима из цепочки α ⊂ (VT ∪ VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим α → β), если α = ξ₁γξ₂, β = ξ₁δξ₂, где ξ₁, ξ₂, δ ⊂ (VT ∪ VN)^*, γ ⊂ (VT ∪ VN)⁺ и правило вывода γ → δ содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Определение: цепочка β ⊂ (VT ∪ VN)^* выводима из цепочки

α ⊂ (VT ∪ VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим α ⇒ β), если существуют цепочки γ₀, γ₁, ... , γ_n (n≥0), такие, что α = γ₀ → γ₁ → ... → γ_n= β.

Определение: последовательность γ₀, γ₁, ... , γ_n называется выводом длины n.

Например, S ⇒ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S → 0A1 → 00A11 → 000A111. Длина вывода равна 3.

Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G)={α ⊂ VT^* | S ⇒ α}.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L(G1) = {0ⁿ1ⁿ | n>0}.

Определение: цепочка α ⊂ (VT ∪ VN)^*, для которой S ⇒ α, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где

    P1:    S → 0A1    P2:    S → 0S1 | 01

        0A → 00A1

        A → ε

эквивалентны, т.к. обе порождают язык

L(G1) = L(G2) = {0ⁿ1ⁿ | n>0}.

Определение: грамматики G1 и G2 почти эквивалентны, если

L(G1) ∪ {ε} = L(G2) ∪ {ε}.

Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на ε.

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где

    P1:    S → 0A1        P2:    S → 0S1 | ε

        0A → 00A1

        A → ε

почти эквивалентны, т.к. L(G1)={0ⁿ1ⁿ | n>0}, а L(G2)={0ⁿ1ⁿ | n≥0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Классификация грамматик и языков по Хомскому

ТИП 0:

Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

ТИП 1:

Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид α → β, где α ⊂ (VT ∪ VN)⁺, β ⊂ (VT ∪ VN)⁺ и | α | | β |.

Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид α → β, где α = ξ₁Aξ₂; β = ξ₁γξ₂; A ⊂ VN; γ ⊂ (VT ∪ VN)⁺; ξ₁,ξ₂ ⊂ (VT ∪ VN)^*.

Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.

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

ТИП 2:

Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A → β, где A ⊂ VN, β ⊂ (VT ∪ VN)⁺.

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A → β, где A ⊂ VN, β ⊂ (VT ∪ VN)^*.

Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную.

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

ТИП 3:

Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A → tB либо A → t, где A ⊂ VN, B ⊂ VN, t ⊂ VT.

Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A → Bt либо A → t, где A ⊂ VN, B ⊂ VN, t ⊂ VT.

Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.

Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых леволинейными грамматиками.

Соотношения между типами грамматик:

(1) любая регулярная грамматика является КС-грамматикой;

(2) любая регулярная грамматика является УКС-грамматикой;

(3) любая КС-грамматика является КЗ-грамматикой;

(4) любая КС-грамматика является неукорачивающей грамматикой;

(5) любая КЗ-грамматика является грамматикой типа 0.

(6) любая неукорачивающая грамматика является грамматикой типа 0.

Замечание: УКС-грамматика, содержащая правила вида A → ε, не является КЗ-грамматикой и не является неукорачивающей грамматикой.

Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.

Соотношения между типами языков:

(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {aⁿbⁿ | n>0}).

(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {aⁿbⁿcⁿ | n>0}).

(3) каждый КЗ-язык является языком типа 0.

Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.

Например, КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и

КС-грамматика G2 = ({0,1}, {S}, P2, S), где

    P1:    S → 0A1    P2:    S → 0S1 | 01

        0A → 00A1

        A → ε

описывают один и тот же язык L = L(G1) = L(G2) = { 0ⁿ1ⁿ | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком,т.к. не существует регулярной грамматики, описывающей этот язык [3].

Примеры грамматик и языков.

1) Язык типа 0: L = {a² | n ≥ 1}

G(L):        S → aaCFD

        F → AFB | AB

        AB → bBA

        Ab → bA

        AD → D

        Cb → bC

        CB → C

        bCD → ε

2) Язык типа 2: L={цепочки из 0 и 1 с одинаковым числом 0 и 1}

G(L):        S → ASB | AB

        AB → BA

        A → 0

        B → 1

3) Язык типа 2: L = {(ac)ⁿ (cb)ⁿ | n > 0}

G(L):        S → aQb | accb

        Q → cSc

4) Язык типа 3: L = {ω ⊥ | ω ⊂ {a,b}⁺, где нет двух рядом стоящих а}

G(L):        S → A⊥ | B⊥

        A → a | Ba

        B → b | Bb | Ab

Разбор цепочек

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

Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.

Определение: вывод цепочки β ⊂ (VT)^* из S ⊂ VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Определение: вывод цепочки β ⊂ (VT)^* из S ⊂ VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке.

Например, для цепочки a+b+a в грамматике

G = ({a,b}, {S,T}, {S → T | T+S; T → a|b}, S)

можно построить выводы:

(1)    S→T+S→T+T+S→T+T+T→a+T+T→a+b+T→a+b+a

(2)    S→T+S→a+S→a+T+S→a+b+S→a+b+T→a+b+a

(3)    S→T+S→T+T+S→T+T+T→T+T+a→T+b+a→a+b+a

Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.

Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия:

(1)    каждая вершина дерева помечена символом из множества (VN ∪ VT ∪ ε), при этом корень дерева помечен символом S; листья - символами из (VT ∪ ε);

(2)    если вершина дерева помечена символом A ⊂ VN, а ее непосредственные потомки - символами a₁, a₂, ... , a_n, где каждое a_i ⊂ (VT ∪ VN), то A → a₁a₂...a_n - правило вывода в этой грамматике;

(3)    если вершина дерева помечена символом A ⊂ VN, а ее единственный непосредственный потомок помечен символом ε, то A → ε - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка α имеет два или более разных левосторонних (или правосторонних) выводов.

Определение: в противном случае грамматика называется однозначной.

Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Пример неоднозначной грамматики:

G = ({if, then, else, a, b}, {S}, P, S),

где P = {S → if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два дерева вывода.

Однако это не означает, что язык L(G) обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной. В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S → if b then S | if b then S’ else S | a

S’ → if b then S’ else S’ | a

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

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:

• A → AA | α
• A → AαA | β
• A → αA | Aβ | γ
• A → αA | αAβA | γ

Пример неоднозначного КС-языка:

L = {aⁱ b^j c^k | i = j или j = k}.

Интуитивно это объясняется тем, что цепочки с i=j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j=k. Но тогда, по крайней мере, некоторые из цепочек с i=j=k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236]. Одна из грамматик, порождающих L, такова:

S → AB | DC

A → aA | ε

B → bBc | ε

C → cC | ε

D → aDb | ε

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящим способом.

При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило вывода, чтобы имеющиеся в нем терминальные символы “проектировались” на символы исходной цепочки.

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.

Преобразования грамматик

Определение: символ x ⊂ (VT ∪ VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V₀ = {S}; i = 1.
2. V_i = {x | x ⊂ (VT ∪ VN), в P есть A → αxβ и A ⊂ V_i-1} ∪ V_i-1.
3. Если V_i ≠ V_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ =

   V_i ∩ VN; VT’ = V_i ∩ VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: символ A ⊂ VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { α ⊂ VT^* | A ⇒ α} пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Метод:

Рекурсивно строим множества N₀, N₁, ...

1. N₀ = ∅, i = 1.
2. N_i = {A | (A → α) ⊂ P и α ⊂ (N_i-1 ∪ VT)^*} ∪ N_i-1.
3. Если N_i ≠ N_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из VN’ ∪ VT; G’ = (VT, VN’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

• обнаруживаются и удаляются все бесплодные нетерминалы.
• обнаруживаются и удаляются все недостижимые символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Задачи.

    a)    S → T | T+S | T-S    b)    S → aSBC | abC

        T → F | F*T        CB → BC

        F → a | b        bB → bb

        Цепочка a-b*a+b .        bC → bc

                cC → cc

                Цепочка aaabbbccc .

2. Построить все сентенциальные формы для грамматики с правилами:

        S → A+B | B+A

        A → a

        B → b

3. Какой язык порождается грамматикой с правилами:

    a)    S → APA    b)    S → aQb | ε

        P → + | -        Q → cSc

        A → a | b

    c)    S → 1B    d)    S → A | SA | SB

        B → B0 | 1        A → a

                B → b

4. Построить грамматику, порождающую язык :

1. L = {aⁿ b^m | n, m ≥ 1}
2. L = {αcβcγc | α, β, γ - любые цепочки из a и b}
3. L = {a₁ a₂ ... a_n a_n ... a₂ a₁ | a_i = 0 или 1, n ≥ 1}
4. L = {aⁿ b^m | n ≠ m ; n, m ≥ 0}
5. L = {цепочки из 0 и 1 с неравным числом 0 и 1}
6. L = {αα | α ⊂ {a,b}⁺}
7. L = {ω | ω ⊂ {0,1}⁺ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.
8. L = {(a^2m b^m)ⁿ | m ≥ 1, n ≥ 0}
9. L = {⊥ | n ≥ 1}
10. L = { | n ≥ 1}
11. L = {| n ≥ 1}

5. К какому типу по Хомскому относится грамматика с правилами:

    a)    S → a | Ba    b)    S → Ab

        B → Bb | b        A → Aa | ba

    c)    S → 0A1 | 01    d)    S → AB

        0A → 00A1        AB → BA

        A → 01        A → a

                B → b

6. Эквивалентны ли грамматики с правилами :

    а)    S → AB    и    S → AS | SB | AB

        A → a | Aa    A → a

        B → b | Bb    B → b

    b)    S → aSL | aL    и    S → aSBc | abc

        L → Kc    cB → Bc

        cK → Kc    bB → bb

        K → b

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

    а)    S → aAb    b)    S → AB | ABS

        aA → aaAb        AB → BA

        A → ε        BA → AB

                A → a

                B → b

8. Построить регулярную грамматику, эквивалентную грамматике с правилами:

    а)    S → A | AS    b)    S → A.A

        A → a | bb        A → B | BA

                B → 0 | 1

9. Доказать, что грамматика с правилами:

        S → aSBC | abC

        CB → BC

        bB → bb

        bC → bc

        cC → cc

порождает язык L = {aⁿ bⁿ cⁿ | n ≥ 1}. Для этого показать, что в данной грамматике

1. выводится любая цепочка вида aⁿ bⁿ cⁿ (n ≥ 1) и
2. не выводятся никакие другие цепочки.

10. Дана грамматика с правилами:

    a)    S → S0 | S1 | D0 | D1    b)    S → if B then S | B = E

        D → H.        Ε → B | B + E

        H → 0 | 1 | H0 | H1        B → a | b

Построить восходящим и нисходящим методами дерево вывода для цепочки:

1. 10.1001
2. if a then b = a+b+b

11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

        S → P⊥

        P → 1P1 | 0P0 | T

        T → 021 | 120R

        R1 → 0R

        R0 → 1

        R⊥→ 1⊥

12. Построить регулярную грамматику, порождающую цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд.

13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.

        L = {a²ⁿ b^m c^2k | m=n+k, m>1}.

14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ), ⊥ }. Сбалансированную цепочку α определим рекуррентно: цепочка α сбалансирована, если

a)    α не содержит скобок,

b)    α = (α₁) или α= α₁ α₂, где α₁ и α₂ сбалансированы.

15. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике.

        L = {aⁿ cb^m caⁿ | n, m>0}.

16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике.

        L = {1ⁿ 0^m 1^p | n+p>m; n, p, m>0}.

17. Дана грамматика G. Определить ее тип; язык, порождаемый этой грамматикой; тип языка.

    G:    S → 0A1

        0A → 00A1

        A → ε

18. Дан язык L = {1³ⁿ⁺² 0ⁿ | n≥0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.

19. Привести пример грамматики, все правила которой имеют вид

A → Bt, либо A → tB, либо A → t, для которой не существует эквивалентной регулярной грамматики.

20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для

1. L1∪L2
2. L1 * L2
3. L1^*

Замечание: L = L1 * L2 - это конкатенация языков L1 и L2 т.е.

L = { αβ | α ⊂ L1, β ⊂ L2}; L = L1^* - это итерация языка L1, т.е. объединение {ε} ∪ L1 ∪ L1*L1 ∪ L1*L1*L1 ∪ ...

21. Написать КС-грамматику для L={ω_i 2 ω_i+1^R | i ⊂ N, ω_i=(i)₂ - двоичное представление числа i, ω^R - обращение цепочки ω}. Написать КС-грамматику для языка L^* (см. задачу 20).

22. Показать, что грамматика

        Ε → E+E | E*E | (E) | i

неоднозначна. Как описать этот же язык с помощью однозначной грамматики?

23. Показать, что наличие в КС-грамматике правил вида

1. A → AA | α
2. A → AαA | β
3. A → αA | Aβ | γ

24. Показать, что грамматика G неоднозначна.

    G:    S → abC | aB

        B → bc

        bC → bc

25. Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества

        X={A ⊂ VN | A ⇒ ε}.

26. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

27. Написать приведенную грамматику, эквивалентную данной.

    a)    S → aABS | bCACd    b)    S → aAB | E

        A → bAB | cSA | cCC        A → dDA | ε

        B → bAB | cSB        B → bE | f

        C → cS | c        C → cAB | dSD | a

                D → eA

                Ε → fA | g

28. Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки языку. Если число шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.

29. Доказать, что любой конечный язык, в который не входит пустая цепочка, является регулярным языком.

30. Доказать, что нециклическая КС-грамматика порождает конечный язык. Нетерминальный символ A ⊂ VN - циклический, если в грамматике существует A ⇒ ξ₁ A ξ₂ . КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.

31. Показать, что условие цикличности грамматики (см. задачу 30) не является достаточным условием бесконечности порождаемого ею языка.

32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен. Циклический символ называется эффективным, если A ⇒ αAβ, где |αAβ|>1; иначе циклический символ называется фиктивным.