Języki, automaty i obliczenia/Ćwiczenia 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych

From Studia Informatyczne

Ćwiczenia 7

Ćwiczenie 1

Niech \displaystyle A = \{a,b\}. Dla automatów
\displaystyle {\mathcal B} = (S_{\mathcal B},A,f_{\mathcal B},s_{\mathcal B},F_{\mathcal B}),\;\;\;\; {\mathcal C} =  (S_{\mathcal C},A,f_{\mathcal C},s_{\mathcal C},F_{\mathcal C})
\displaystyle S_{\mathcal B} = \{s_{\mathcal B},s_1,s_2\},  \;\;F_{\mathcal B} = \{s_2\},\;\;\; S_{\mathcal C} = \{s_{\mathcal C},s\},\;\; F_{\mathcal C} = \{s\},

gdzie

\displaystyle \begin{array} {c|c|c|c|} f_{\mathcal B} &s_{\mathcal B} &s_1 & s_2 \\  \hline a & s_2 & s_1 & s_2 \\ \hline b & s_1 & s_1 & s_2\\  \hline \end{array}  \hspace{2cm} \begin{array} {c|c|c|} f_{\mathcal C} &s_{\mathcal C} &s \\ \hline a & s & s \\  \hline b & s_{\mathcal C} & s_{\mathcal C} \\ \hline \end{array}
skonstruuj automat \displaystyle \mathcal A taki, że
\displaystyle L({\mathcal A}) = L({\mathcal B}) \cap L({\mathcal C}),

Rozwiązanie

\displaystyle L({\mathcal A})= (S_{\mathcal B}\times S_{\mathcal C},A,f_{\mathcal A},(s_{\mathcal B},s_{\mathcal C}), F_{\mathcal B}\times  F_{\mathcal C}). Funkcja przejść zadana jest grafem

<flash>file=ja-lekcja07-c-rys1.swf|width=250|height=250</flash>

Rysunek 1

Zauważ, że otrzymany automat nie jest minimalny. Jakie języki akceptują automaty \displaystyle {\mathcal A}, \displaystyle {\mathcal B} i \displaystyle {\mathcal C}?

Ćwiczenie 2

Niech \displaystyle A = \{a,b\}. Dla automatu
\displaystyle {\mathcal B} = (S_{\mathcal  B},A,f_{\mathcal B},s_{\mathcal B},F_{\mathcal B}),

gdzie

\displaystyle S_{\mathcal B} = \{s_{\mathcal B},s_1,s_2\},  \;\;F_{\mathcal B} = \{s_1\},

a funkcja przejść zdefiniowana jest następująco:

\displaystyle \begin{array} {c|c|c|c|} f_{\mathcal B} &s_{\mathcal B} &s_1 & s_2 \\  \hline a & s_1 & s_2 & s_2 \\ \hline b & s_1 & s_{\mathcal{B}} & s_1\\  \hline \end{array}

skonstruuj automat deterministyczny \displaystyle \mathcal A taki, że

\displaystyle L({\mathcal A}) = L({\mathcal B})^*.

Wskazówka

Pomocne może być użycie automatu z pustymi przejściami.

Rozwiązanie

Automat \displaystyle \mathcal{B} pokazany jest na rysunku 2.

<flash>file=ja-lekcja07-c-rys2.swf|width=250|height=150</flash>

Rysunek 2

Aby skonstruować automat akceptujący język \displaystyle L(\mathcal{B})^*,

wystarczy dodać przejście \displaystyle f(s_1,1)=s_{\mathcal{B}} (dlaczego?). Automat z pustymi przejściami akceptujący \displaystyle L(\mathcal{B})^* pokazany jest na rysunku 3.

<flash>file=ja-lekcja07-c-rys3.swf|width=250|height=150</flash>

Rysunek 3

Po usunięciu pustych przejść otrzymujemy automat z rysunku 4:

<flash>file=ja-lekcja07-c-rys4.swf|width=250|height=250</flash>

Rysunek 4

Teraz wystarczy skonstruować równoważny automat deterministyczny.

Ćwiczenie 3

Dane są dwa automaty nad tym samym alfabetem \displaystyle A
\displaystyle \mathcal{A}=(S,f,s_{0},T) i \displaystyle \mathcal{B}=(Q,g,t_{0},F). Udowodnij, że istnieje liczba \displaystyle  p\in{\Bbb N}_{0} taka, że jeśli dla każdego słowa \displaystyle w o długości \displaystyle |w|\leq p spełniona jest implikacja \displaystyle w\in L(\mathcal{A})\Rightarrow w\in L(\mathcal{B}), to

\displaystyle L(\mathcal{A})\subseteq L(\mathcal{B})

Rozwiązanie

Niech \displaystyle \mathcal{C} będzie automatem takim, że \displaystyle L(\mathcal{C})=L(\mathcal{A})\cup L(\mathcal{B}). Wówczas,

\displaystyle L(\mathcal{C})\subseteq L(\mathcal{B})\Leftrightarrow L(\mathcal{A})\subseteq L(\mathcal{B}).

Udowodnimy więc inkluzję \displaystyle L(\mathcal{C})\subseteq L(\mathcal{B}), gdzie

\displaystyle \mathcal{C}=(S\times Q,f\times g,(s_0,t_0), (S\times F \cup T\times Q)).

Przyjmijmy \displaystyle p=|S| \cdot |Q|. Niech \displaystyle w \in L(\mathcal{C})

  1. Jeśli \displaystyle |w|\leq p, to z założenia \displaystyle w \in L(\mathcal{B})
  2. Jeśli \displaystyle |w|>p, to z lematu o pompowaniu wynika, że \displaystyle \exists v_1 v_2 \in A^*, \displaystyle \exists u \in A^+ takie, że \displaystyle w=v_1 uv_2, \displaystyle v_1 v_2 \in L(\mathcal{C}) i \displaystyle |v_1v_2|<|w|.
\displaystyle (f\times g)((s_0,t_0),w) =   (f\times g)((s_0,t_0),v_1 v_2)=(f(s_0,v_1v_2),g(t_0,v_1v_2)) \in S\times F \cup T\times Q

Mamy dwie możliwości:

(a) \displaystyle g(t_0,v_1v_2) \in F, co oznacza \displaystyle v_1v_2 \in L(\mathcal{B}), \displaystyle w \in  L(\mathcal{B}),
(b) \displaystyle  f(s_0,v_1v_2)\in T, co oznacza \displaystyle v_1v_2 \in L(\mathcal{A}).
Jeśli \displaystyle |v_1v_2|<p, to \displaystyle v_1v_2 \in L(\mathcal{B}), \displaystyle w \in L(\mathcal{B}).
Jeśli \displaystyle |v_1v_2|>p, to powtarzamy punkt 2.

Po każdym kroku długość rozważanego słowa silnie maleje, więc po skończonej ilości kroków uzyskamy oczekiwany efekt.
Zauważ, że z zadania tego wynika rozstrzygalność problemu równoważności automatów. Algorytmiczny aspekt tego problemu rozważymy w ćwiczeniach 8.

Ćwiczenie 4

Niech \displaystyle A będzie dowolnym alfabetem, a \displaystyle L \subset A^* językiem regularnym. Udowodnij, że język \displaystyle L'=\{a^{|w|} :w \in L\} jest też językiem regularnym.

Rozwiązanie

Rozważmy homomorfizm \displaystyle h:A^* \longrightarrow \{a\}^* taki, że \displaystyle \forall  x \in A\displaystyle \quad f(x)=a. Dla tak zdefiniowanego \displaystyle h język \displaystyle L' jest homomorficzym obrazem języka regularnego \displaystyle L'=h(L), a więc jest regularny.

Ćwiczenie 5

Udowodnij, że następujące języki nie są regularne:

  1. \displaystyle L = \{a^n : n \; \text{nie jest liczbą pierwszą\;} \},
  2. \displaystyle L=\left\{ a^{n}b^{m}:0\leq n,m;\;n\neq m\right\}.

Rozwiązanie punktu 1

Skorzystamy z faktu, że język \displaystyle L' = \{a^n : n  \; \text{ jest liczbą pierwszą\;} \} nie jest akceptowany ( ćwiczenie 8), a więc nie jest regularny.

\displaystyle a^*=L \cup L', L\cap L' = \emptyset, \;\text {a więc}\;L'=\overline{L}.

Ponieważ klasa języków regularnych jest zamknięta ze względu na uzupełnienie, to \displaystyle  L \notin \mathcal{REG}.

Rozwiązanie punktu 2

Język \displaystyle L'=\left\{ a^{n}b^{n}:0\leq n \right\} nie jest akceptowany (patrz 3.1. z wykładu 6), a więc nie jest regularny.

\displaystyle a^*b^* =L \cup L',L\cap L' = \emptyset,\;\text {a więc}\;L'=a^* b^* \cap\overline{L}.

Ponieważ klasa języków regularnych jest zamknięta ze względu na uzupełnienie i przecięcie, to \displaystyle  L \notin \mathcal{REG}.

ZADANIA DOMOWE

Ćwiczenie 6

Niech \displaystyle A = \{a,b\}. Skonstruuj automat \displaystyle \mathcal A, taki że

1. \displaystyle L({\mathcal A}) = L({\mathcal B}) \cup L({\mathcal C}), gdzie
\displaystyle {\mathcal B} =  (S_{\mathcal B},A,f_{\mathcal B},s_{\mathcal B},F_{\mathcal B}),\;\;\;\; {\mathcal C} =  (S_{\mathcal C},A,f_{\mathcal C},s_{\mathcal C},F_{\mathcal C}),
\displaystyle S_{\mathcal B} =  \{s_{\mathcal B},s_1,s_2\}, \;\;F_{\mathcal B} = \{s_2\},\;\;\; S_{\mathcal C} =  \{s_{\mathcal C},{s'}_1,{s'}_2\},\;\; F_{\mathcal C} = \{{s'}_2\},


\displaystyle \begin{array} {c|c|c|c|} f_{\mathcal B} &s_{\mathcal B} &s_1 & s_2 \\  \hline a & s_2 & s_1 & s_2 \\ \hline b & s_1 & s_1 & s_2\\ \hline \end{array}  \hspace{2cm}  \begin{array} {c|c|c|c|} f_{\mathcal C} &s_{\mathcal C} &{s'}_1&{s'}_2 \\ \hline a & {s'}_1 & {s'}_1& {s'}_2 \\  \hline b & {s'}_2 & {s'}_1& {s'}_2 \\ \hline \end{array}
2. \displaystyle L({\mathcal A}) = L({\mathcal B})^*, gdzie
\displaystyle {\mathcal B} =  (S_{\mathcal B},A,f_{\mathcal B},s_{\mathcal B},F_{\mathcal B}),
\displaystyle S_{\mathcal B} = \{s_{\mathcal B},s_1,s_2,s_3\}, \;\;F_{\mathcal  B} = \{s_2\},


\displaystyle \begin{array} {c|c|c|c|c|} f_{\mathcal B} &s_{\mathcal B} &s_1 & s_2 & s_3\\ \hline a & s_1 & s_3 & s_3 & s_3 \\  \hline b & s_3 & s_2 & s_3 &s_3\\ \hline \end{array}

Podaj dwie konstrukcje:

  1. opartą na dowodzie twierdzenia Kleene'ego,
  2. z wykorzystaniem automatu z pustymi przejściami.

Ćwiczenie 7

Skonstruuj minimalny automat \displaystyle \mathcal{A}, taki że \displaystyle L(\mathcal{A})=L(\mathcal{B})^*, gdzie \displaystyle \mathcal{B} opisany jest

poniższym grafem:



Rysunek 5


Ćwiczenie 8

Udowodnij, że następujące języki nie są regularne:

  1. \displaystyle L=\left\{ a^{n}b^{m}c^n:0<n,m\right\},
  2. \displaystyle L = \{(ab)^n(bc)^n : n \geq 0 \}.

Wskazówka do punktu 2

Wykorzystaj fakt, że język \displaystyle \left\{ a^{n}b^{n}:n \geq 0\right\} nie jest regularny oraz domkniętość klasy języków regularnych ze względu na homomorfizm.

Ćwiczenie 9

Zbuduj automat akceptujący język będący ogółem skończonych sekwencji binarnych, w których liczba zer jest podzielna przez dwa, a liczba jedynek przez 3, a następnie gramatykę generującą ten język.

Wskazówka

Stany automatu niech będą postaci \displaystyle (x,y), gdzie \displaystyle x \in  \{0, 1\}, \displaystyle y \in \{0, 1, 2\}. Stan początkowy to \displaystyle (0,0). Określ funkcję przejść w ten sposób, że po przeczytaniu przez automat słowa zawierającego \displaystyle k symboli 0 oraz \displaystyle l symboli 1 automat znajdzie się w stanie \displaystyle (k \mod 2, l \mod 3). Zastanów się, który stan będzie stanem końcowym. Na podstawie automatu określ gramatykę.