ТМВ-2020-Лекция-10.03.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Разбор контрольной работы №1

Задача № 1

1 вариант

Построить ДКА для языка \(L\)

$$L =\{\,\omega\in\{0, 1\}^*\mid\omega$$ начинается с 1, имеет чётную длину, после каждого 0 следует 1 $$\}$$

Решение:


2 вариант

Построить ДКА для языка регулярного выражения

\(a(a^*+ba)(b^*+a)\)

Решение:

ДКА для языка регулярного языка.png

Задача № 3

1 Вариант


Восстановить регулярное выражение из данного НКА:

Восстановить регулярное выражение.png

Решение:

Сперва добавляем новые начальную и конечную вершины автомата:

Восстановить регулярное выражение(1).png

Далее выгодно выбрать состояния, где меньше всего путей, и удалять эти вершины:

Восстановить регулярное выражение(3).png
Восстановить регулярное выражение(4).png

Итоговый результат:

Восстановить регулярное выражение(5).png

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

2 вариант

Восстановить регулярное выражение из данного НКА:

Восстановить регулярное выражение(11).png

Решение:

Восстановить регулярное выражение(12).png
Восстановить регулярное выражение(133).png


Восстановить регулярное выражение(144).png


Восстановить регулярное выражение(155).png
Восстановить регулярное выражение(166).png
Восстановить регулярное выражение(17).png

Задача № 4

1 вариант

Верно ли равенство:

\(b+ab*+aa*b+aa*ab ?= a*(b+ab*)\)

\(a*(b+ab*)=a*b+a*ab*\)

\(a*b=b+aa*b\)

\(a*ab*=aa*b*=a+aa*+aa*b+ \ldots \)

\(aa*b \subset a*ab* \)

\(b+aa*b+aa*b*=b+aa*b*\)  равенство верно

2 вариант

Верно ли равенство:

\( a*(b+ab*)?=b+ab*+aa*b+aa*ab* \)

\(b+ab*+aa*b+aa*ab*=(\epsilon+aa*)(b+ab*)=a*(b+ab*)\) равенство верно

Задача № 5

1 вариант

Привести примеры языков:

1) \(L_1, L_2 - нерегулярные, L_1 \cup L_2 регулярный\)

Решение:

\(a^nb^n\) - нерегулярный

\(a^nb^*\) - регулярный

\(a^nb^n/a^nb^* = {a^nb^k | k \neq n}\) - нерегулярный

2) \(L_1, L_2 - нерегулярные, L_1 \cap L_2\) - нерегулярный и бесконечный \((L \neq {\epsilon})\)

Решение:

\(L_1=a^nb^n\)

\(L_2=a^nb^nc^*\)

\(L_1 \cap L_2= a^nb^n\)

3) \(L_1\) - регулярный, \(L_2\) - нерегулярный, а \( L_1 \cup L_2\) - регулярный

Решение:

\(L_1=a^nb^*\)

\(L_2=a^nb^n\)

\(L_1 \cup L_2 = a^nb^*\)

2 вариант

Дано: \(x_1,x_2 \subset \Sigma^*\)

Доказать, что \(L_1\) - регулярный

\(L_1 = \{\omega \in \Sigma^* | x_1, x_2\) - подстроки \(\omega\}\)

\(x_1 = x_{11}x_{12} \ldots x_{1n}\)

\(x_2 = x_{21}x_{22} \ldots x_{2m}\)

Случаи:

  • \(x_1\) не пересекается с \(x_2\) в \(\omega\)
    Доказать, что язык регулярный(x1 не пересекается с x2) в слове.png

  • \(x_1\) пересекается с \(x_2\) в \(\omega\)

\(x_1 = x_{11}x_{12} \ldots x_ {1l}x_{1 l+1}\ldots x_{1n}\)

\(x_2 = x_{21}x_{22} \ldots x_ {2l}x_{2 l+1}\ldots x_{2m}\)

\(x_3 = x_{11} \ldots x_{1 n-l-1}x_{21} \ldots x_{2m}\)

Доказать, что язык регулярный(2).png


  • \(L_1 = \{\omega \in \Sigma^* | \omega\) начинается с \(x_1\) оканчивается на \(x_2\}\)
Доказать, что язык регулярный(3).png
  • \(L_1 = \{\omega \in \Sigma^* | \omega\) содержит хотя бы 2 непересекающиеся копии \(x_1\}\)
Доказать, что язык регулярный(4).png