Теория автоматов. Лекция 1 Основные понятия теории конечных автоматов. Элементы логикоматематического языка. 59
![]()
|
Задание 2.1. (вариант 2) Задана формальная грамматика G =<T, N,S,P >, где T ={a,b}, N ={A,B,S}, множество продукций P определенно следующим образом. S → AbA| AAbBbA → AAab| BAABAA→bb | A A→bb a| B → AA|b Какие из следующих записей являются выводами в грамматике G (Указать правильные варианты ответов).
Задание 2.1. (вариант 3) Задана формальная грамматика G =<T, N, S, P >, где T ={a,b}, N ={A,B,S}, множество продукций P определенно следующим образом. S → AbA| AAbBbA → AAab| BAABAA→bb | A A→bb a| B → AA|b Какие из следующих записей являются выводами в грамматике G (Указать правильные варианты ответов).
Задание 2.1. (вариант 4) Задана формальная грамматика G =<T, N, S, P >, где T ={a,b}, N ={A,B,S}, множество продукций P определенно следующим образом. S → AbA| AAbBbA→ AAab | BAABAA→bb| A A→bb a| B → AA| b Какие из следующих записей являются выводами в грамматике G (Указать
Решение: Несложно увидеть, что существует два «типа» выводов в данной грамматике. Первый начинается с последовательности S, AbA, второй с последовательности S, AB. Рассмотрим вывод, начинающийся с S, AbA. Здесь можно произвольное (целое неотрицательное) число раз применять продукцию A→ aA к «левому» либо «правому» нетерминальному символу A, после чего дважды применить продукцию A→λ и тем самым построить вывод S, AbA,..., aaaAbaaaAaaabaaa... .. , ... .. . Это позволяет вывести в грамматике G все слова множества {a ban m | ,n m∈ Z+}. Рассмотрим вывод, начинающийся с S, AB. Здесь можно произвольное (целое неотрицательное) число раз применять продукцию A→ aA, после чего один раз применить продукцию A→λ, дополнительно можно один раз применить продукцию B →b. Таким образом будет построен вывод S, AB,...,aa ab... . Это позволяет вывести в грамматике G все слова множества {a b nn | ∈ Z }+ . Объединив два множества слов терминального алфавита, получаемых в результате выводов двух возможных «типов», находим L G( ) ={a ban m | ,n m∈Z }+ ∪{a b nn | ∈Z }+ . Задание 2.2. (вариант 2) Задана КСГ G =<T, N, ,S P >, где T ={a b, }, N ={A,B,S}, множество продукций P определенно следующим образом. S → AaA| AaBA→ aA|λB →b Определить язык, порождаемый грамматикой G (Указать правильный вариант ответа).
Задание 2.2. (вариант 3) Задана КСГ G =<T, N, ,S P >, где T ={a b, }, N ={A,B,S}, множество продукций P определенно следующим образом. S→ AbAA| BBAA→ aA|λB→b Определить язык, порождаемый грамматикой G (Указать правильный вариант ответа).
Задание 2.2. (вариант 4) Задана КСГ G =<T, N, S, P >, где T ={a b, }, N ={A,B,S}, множество продукций P определенно следующим образом. S →bABAb | BABA→ aA a| B →b Определить язык, порождаемый грамматикой G (Указать правильный вариант ответа).
Задание 2.3. (вариант 1) Какие из следующих языков являются контекстно-свободными (Указать правильные варианты ответов).
Решение:
Тогда рассмотрим возможные способы разбиение слова α.
α(2) = a bk 2k a k l+ (ξ ξ1+ 2) и т.к. l(ξ1 2ξ ) ≠ 0, то α(2)∉ L.
Получаем противоречие. Таким образом предположение неверно и L не является контекстно-свободным.
следующую контекстно-свободную грамматику, порождающую L: S → aSa aSb bSa bSb a| | | |
S → AB A → aA a| B → aBb ab|
Докажем от противного, используя лемму о разрастании, что L не является контекстно-свободным. Предположим, что L – контекстносвободный. Согласно лемме существует константа k и слово α= akbk #a bk k (α∈L и l( )α = 4k +1≥ k ) может быть представлено в виде α= β1ξ1γξ2β2 , что выполняются условия леммы о разрастании. Если ξ1 или ξ2 содержат букву #, то α(2)∉ L в силу того, что будет содержать две буквы #. Далее будем считать, что ξ1,ξ2 ∈{a b, }*. Тогда рассмотрим возможные способы разбиение слова α.
Получаем противоречие. Таким образом, предположение неверно и L не является контекстно-свободным.
L. Способ 1. S → aAa bAb| A → aA bA| |λ Способ 2. Языка L является регулярным, тогда построим конечный автомат K , распознающий язык L. Используя конечный автомат K , построим соответствующую ему грамматику G типа 1, порождающую язык L. Класс грамматик типа 1 включен в класс грамматик типа 2 (класс контекстно-свободных грамматик). Таким образом, построенная грамматика G будет являться контекстно-свободной. Конечный автомат K : ![]() Соответствующая грамматика G =<T, N, ,S P >, где T = {a b, }, N = {q0 ,q q1, 2,q q3, 4}, S = q0 и множество продукций P определяется следующим образом: q0 → aq1 | bq3q1 → aq1 | bq2 |λq2 → aq1 | bq2q3 → aq4 | bq3 |λq4 → aq4 | bq3 Задание 2.3. (вариант 2) Какие из следующих языков являются контекстно-свободными (Указать правильные варианты ответов).
Задание 2.3. (вариант 3) Какие из следующих языков являются контекстно-свободными (Указать правильные варианты ответов).
|