Исправлены упражнения на теория языка, автоматы и грамматики. За упражнениями следует коррекция.

Распознанные слова

Упражнение 1

Укажите все слова размеров 0, 1, 2, 3 и 4 следующих правильных языков: (a + ba)* ; а (аа + б (аб) *имеет)*имеет. Для этого вы можете сделать дерево возможности для каждого из языков.

Слова длины 0: эпсилон; Слова длины 1: а; Слова длины 2: аа, ба; Слова длины 3: ааа, аба, баа; Слова длины 4: аааа, ааба, абаа, баба, бааа.

Слова длины 0: нет; Слова длины 1: нет; Слова длины 2: аа; Слова длины 3: нет; Слова длины 4: аааа, абаа.

Упражнение 2

Укажите все слова длины 0, 1, 2, 3 и 4, распознаваемые следующими автоматами. На этот вопрос можно ответить систематически, используя матрицы. Для этого мы представляем автомат (который мы можем видеть как график) по матрице смежности. Таким образом, индексный коэффициент i, j матрицы Mк соответствует словам длины k, распознаваемым автоматом, если начальным состоянием было состояние i, а конечным состоянием — состояние j. Если мы хотим получить слова длины k, распознаваемые нашим автоматом, достаточно умножить матрицу саму на себя.

Исправлены упражнения по теории языков, автоматов и грамматик. За упражнениями следует коррекция.

Для автомата A1 достаточно вычислить (1,3) и (1,4) следующих матриц:

Исправленные упражнения по теории языков, автоматов и грамматик

Слова длины 0: нет; Слова длины 1: б; Слова длины 2: аб + аа + ба; Слова длины 3: аба + абб + ааа + баа; Слова длины 4: абаа + абаб + абба + аббб + аааа + бааа.

Для автомата A1 достаточно вычислить (1,1) и (1,2) следующих матриц:

Исправленные упражнения по теории языков, автоматов и грамматик

Слова длины 0: M0 1.1 + M0 1.2 = ; Слова длины 1: М1 1,1 + М1 1,2 = а; Слова длины 2: M2 1.1 + M2 1.2 = aa + bb; Слова длины 3: М3 1,1 + М3 1,2 = ааа + бба + абб; Слова длины 4: М4 1,1 + М4 1,2 = аааа + абба + аабб + ббаа + ббаб

Упражнение 3

Рассмотрим следующий автомат M:

Исправленные упражнения по теории языков, автоматов и грамматик

Сколько состояний имеет автомат M? Дайте множество конечных состояний и множество состояний

Инициалы. Является ли автомат детерминированным? В каком состоянии находится автомат после прочтения слова bbabbb? Это слово распознается/принимается ПЛК? Те же вопросы к слову babaabba.

Сделайте автомат M полным. Распознается ли этот автомат словом baa? принимается этой машиной?

Рассмотрим следующий автомат N:

Исправленные упражнения по теории языков, автоматов и грамматик

В каких состояниях может находиться автомат N после прочтения babba? Принимается ли это слово этим автоматом? Тот же вопрос для слова abbb.

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

Чтобы прочитать первое слово: 1 ⊢ b1 ⊢ bb1 ⊢ bba2 ⊢ bbab3 ⊢ bbabb4 ⊢ bbabbb2 или 2 не является конечным состоянием, поэтому оно распознается, но не принимается. Принцип вывода тот же, если автомат детерминирован, в противном случае необходимо построить дерево вывода.

Чтобы прочитать последнее слово:

Исправленные упражнения по теории языков, автоматов и грамматик

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

Построить автомат

Упражнение 4

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

  • L — это язык, обозначаемый aba + bab.
  • L - это язык, обозначаемый (аба)*+ (баб)*.
  • L = {и ∈ {а, Ь}* такой, что u содержит множитель bbb}.
  • L = {и ∈ {а, Ь}* такое, что u не содержит множителя bbb

Упражнение 5

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

  • Язык слов, содержащих хотя бы один раз букву а
  • Язык слов, содержащих не более одного раза букву а
  • Язык слов, содержащих четное число раз букву а
  • Язык слов, допускающий аба как фактор

Признанный язык

Упражнение 6

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

Исправленные упражнения по теории языков, автоматов и грамматик

Упражнение 7

 Будь там грамматика G = ({а, Ь, с}, {S, А}, S, Р); где P содержит следующие правила: S → aS | бА; А → ок | ε

Определите, порождены ли G слова w1 = abac, w2 = aabccc, w3 = cabbac и w4 = ab. Найдите язык, порожденный G (обозначается L(G)).

Слова w1 и w3 не порождены G; слова w2 и w4 порождены G: S ⊢ aS ⊢ aaS ⊢ aabA ⊢ aabcA ⊢ aabccA ⊢ aabcccA ⊢ w2, а для w4: S ⊢ aS ⊢ abA ⊢ ab = w4.

Чтобы найти язык, напишите автомат, сгенерированный грамматикой, а затем используйте метод по вашему выбору, чтобы получить его регулярное выражение: a* bc*.

Упражнение 8

Пусть грамматика g = <{a, b, c}, {S, A, B}, S, P>, где: P = {S → aA | е; А → бА | КБ; Б → бБ | имеет }.

Найдите систему уравнений (изобычные выражения) соответствие. Решите эту систему.

Мы свяжем переменную с каждым нетерминалом g: X0 (связанный с S), X1 (с A) и X2 (с B). Мы переводим правила производства P в уравнения регулярных выражений:

Исправленные упражнения по теории языков, автоматов и грамматик

Применяя теорему Ардена к третьему уравнению, получаем: X2 = b*a. Заменив X2 во втором уравнении, получим: X1 = b.X1 + cb*a; то по теореме Ардена получаем: X1 = b*cb*a. Подставим в первое уравнение и получим: X0 = ab*cb*a + ε, что обозначает язык, порожденный g.

Упражнение 9

Пусть грамматика g = <{a, b, c}, {S, A, B}, S, P>, где: P = {S → baA | как | е; А → аА | бБ | е; Б → ЦБ | аА}.

Постройте простой конечный автомат A, эквивалентный g. Напишите систему уравнений, связанную с A. Найдите регулярное выражение, обозначающее L(A).

Чтобы найти простой автомат, связанный с g, мы можем разложить правило S → baA на два правила: S → bC и C → aA; где C — новый нетерминал. Мы строим эквивалентный простой автомат A, связывая состояние автомата с каждым нетерминалом, это состояние будет окончательным, когда связанный с ним нетерминал производит ε. Переходы A будут выведены из продукционных правил g.

Исправленные упражнения по теории языков, автоматов и грамматик

Система регулярных уравнений, связанных с A:

Исправленные упражнения по теории языков, автоматов и грамматик

Чтобы найти регулярное выражение, которое обозначает L(A), мы решаем систему, чтобы найти значение X0. Из четвертого уравнения имеем: X3 = c*aX2; заменим в третьем: X2 = aX2 +bc*aX2 + ε = (a +bc*a)X2 +ε, что сводится к X2 = (a +bc*a)*. Заменим во втором: X1 = a(a +bc*a)*. Тогда в первом: X0 = aX0 + ba(a + bc*a)* + ε. Таким образом, мы получаем решение: X0 = a*(ba(a +bc*a)* +ε). Таким образом, L(A) обозначается регулярным выражением: a*ba(a+ bc*a)* +a*.

Делиться
ru_RURU