Test GR3: Różnice pomiędzy wersjami

Aktualna wersja na dzień 11:02, 5 wrz 2023

--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---

Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności, dziedzin i kodziedzin morfizmów.

Prawda Źle

Fałsz Dobrze

Zaznacz zdania prawdziwe dotyczące podłogi i sufitu:

$n \geq 2^{⌈ \log_{2} n ⌉}$ ,

$n \leq 2^{⌈ \log_{2} n ⌉}$ ,

$⌈ \log_{2} ⌈ n / 2 ⌉ ⌉ = ⌈ \log_{2} (n / 2) ⌉$ ,

$⌊ \log_{2} ⌈ n / 2 ⌉ ⌋ = ⌊ \log_{2} (n / 2) ⌋$ .

Dowolny niepusty podzbiór $S \subseteq ℕ$ zbioru liczb naturalnych

ma w sobie liczbę największą

ma w sobie liczbę najmniejszą

ma w sobie liczbę największą oraz liczbę najmniejszą

ma w sobie liczbę najmniejszą ale nigdy nie ma największej

Zbiór $S \subseteq ℕ$ jest taki, że jeśli $s \in S$ to $s + 1 \in S$ . Jeśli $9 \in S$ , to:

$S = ℕ$

$S = ℕ - {0, 1, 2, 3, 4, 5, 6, 7, 8}$

$S \subseteq ℕ - {0, 1, 2, 3, 4, 5, 6, 7, 8}$

$S \supseteq ℕ - {0, 1, 2, 3, 4, 5, 6, 7, 8}$

Zbiór $S \subseteq ℕ$ jest taki, że jeśli $a, b \in S$ , to $a + b \in S$ oraz $a + b + 1 \in̸ S$ . Jeśli $0, 2 \in S$ , to:

$S = ℕ$

zbiór $S$ zawiera wszystkie liczby naturalne, które są parzyste

zbiór $S$ jest zawarty w zbiorze liczb naturalnych, które są parzyste

zbiór $S$ jest zbiorem wszystkich liczb naturalnych, które są parzyste

Ostatnią cyfrą liczby $3^{3^{n}}$ jest:

zawsze $3$

zawsze $3$ lub $7$

zawsze $7$

jakakolwiek z cyfr $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$

Jeśli $Z \subseteq ℕ$ jest jakimś zbiorem liczb naturalnych, który wraz z każdym początkowym fragmentem zbioru $ℕ$ postaci ${0, \dots, k - 1}$ zawiera również kolejną liczbę $k$ , to wtedy

zbiór $Z$ zawiera wszystkie liczby naturalne poza skończonym podzbiorem

zbiór $Z$ zawiera wszystkie liczby naturalne

zbiór $Z$ zawiera nieskończenie wiele liczb naturalnych

zbiór $Z$ jest pusty

Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?

klasa na pewno się nie pogodzi

klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia

jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić

jeżeli w klasie byłyby już co najmniej dwie osoby, przy czym osoby w klasie byłyby ze sobą pogodzone, to reszta klasy miałaby szansę się pogodzić

Jeśli $S \subseteq ℕ$ , to:

zbiór $S$ ma element największy

zbiór $S$ ma element najmniejszy

zbiór $S$ ma element największy, o ile $S$ jest niepusty

zbiór $S$ ma element najmniejszy, o ile $S$ jest niepusty

Test GR3: Różnice pomiędzy wersjami

Aktualna wersja na dzień 11:02, 5 wrz 2023

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-==Wyrażenia regularne==
+--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---
-{{definicja|1.1||
-Niech <math>{A}</math> będzie skończonym alfabetem. Rodzina <math>\mathcal{REG}(A^{*}) </math> '''języków regularnych''' nad alfabetem <math>A</math>  to najmniejsza, w sensie inkluzji, rodzina <math>\mathcal{R} </math> języków zawartych w  <math>A^*</math> taka, że:
+<quiz type="exclusive">
+Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które
+spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności,
+dziedzin i kodziedzin morfizmów.
+<wrongoption>Prawda</wrongoption>
+<rightoption>Fałsz</rightoption>
+</quiz>
+---------------------------------------------------------------------
-: (1) <math>\emptyset \in\mathcal{R} </math>, <math>\forall a \in A \;\;\; \{ a \} \in\mathcal{R} </math>
-: (2) jeśli <math>X, Y \in\mathcal{R} </math>, to <math>X \cup Y, \;\; X \cdot Y \;\; \in\mathcal{R} </math>
+<quiz>
+Zaznacz zdania prawdziwe dotyczące podłogi i sufitu:
+<option><math>n\geq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option>
+<option><math>n\leq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option>
+<option><math>\left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil</math>,</option>
+<option><math>\left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor</math>.</option>
+</quiz>
-: (3) jeśli <math> X \in\mathcal{R} </math>, to <math>X^* = \bigcup_{n=0} ^\infty X^n \in\mathcal{R} </math>
-}}
-Wprost z definicji wynika, że <math>\left\{ 1\right\} =\emptyset ^{*}\in \mathcal{R} </math> oraz że dla dowolnego języka regularnego zachodzi równość <math>X\in \mathcal{R} </math> jest
-<center><math>X^{+}=\bigcup ^{\infty }_{n=1}X^{n}=X\cdot X^{*}\in \mathcal{R}.</math></center>
+<quiz>
+Dowolny niepusty podzbiór  <math>S\subseteq \mathbb{N}</math>  zbioru liczb naturalnych
-Wprowadzona w ten sposób definicja rodziny języków regularnych wymaga
-uzasadnienia faktu, iż definiowany obiekt, definiowana rodzina, istnieje. Zauważmy więc, że warunki 1-3 definicji 1.1 spełnia na przykład rodzina <math>\mathcal{P}(A^{*}) </math> wszystkich podzbiorów  <math>A^*</math>, a zatem klasa takich rodzin nie jest pusta. Ponadto łatwo możemy stwierdzić, że jeśli rodziny <math>\mathcal{R}_{1},\: \mathcal{R}_{2} </math> spełniają warunki 1-3  powyższej definicji, to rodzina <math>\mathcal{R}_{1}\cap \mathcal{R}_{2} </math> również spełnia te warunki. Stąd możemy wyprowadzić wniosek, że najmniejsza rodzina spełniającą te warunki, to przecięcie
+ma w sobie liczbę największą
-<center><math>\mathcal{REG}(A^{*})=\bigcap \mathcal{R},</math></center>
+ma w sobie liczbę najmniejszą
-po wszystkich rodzinach <math>\mathcal{R} </math> spełniających warunki 1-3 definicji 1.1.
-Zauważmy, że w świetle powyższej definicji fakt, że <math>X \in\mathcal{REG}(A^{*}) </math> oznacza, że <math>X</math> można
+ma w sobie liczbę największą oraz liczbę najmniejszą
-uzyskać z liter alfabetu i zbioru pustego <math>\emptyset</math> poprzez zastosowanie wobec tych "elementarnych klocków" skończonej liczby działań: sumy, katenacji i gwiazdkowania. Na odwrót, każdy zbiór otrzymany w ten sposób jest elementem rodziny <math>\mathcal{REG}(A^{*}) </math>. Ta obserwacja prowadzi do pojęcia wyrażeń regularnych, formalnego zapisu języków regularnych.
-{{definicja|1.2||
-Niech <math>{A}</math> będzie  alfabetem, a zbiór <math>\{+ , \star , \emptyset , (,)\}</math> alfabetem   rozłącznym z <math>{A}</math>. Słowo <math>{\bf \alpha} \in {\bf (}A \cup \{ + , \star , \emptyset , (,)\}{\bf )}^*</math> jest '''wyrażeniem regularnym ''' nad alfabetem <math>{A}</math> wtedy i tylko wtedy, jeśli:
-: (1) <math>{\bf \alpha} = \emptyset</math>
-: (2) <math>{\bf \alpha} = a \in A \;\; ({\bf \alpha}</math> jest literą)
-: (3) <math>{\bf \alpha}</math> jest w postaci <math> ({\bf \beta} + {\bf \gamma}), ({\bf \beta} {\bf \gamma} ), {\bf \gamma} ^* </math>, gdzie <math> {\bf \beta}, {\bf \gamma} </math>są wyrażeniami regularnymi nad alfabetem <math>{A}</math>.
-Przyjmujemy oznaczenia:
-<center><math>\emptyset ^{*}=1 \;\;\text{ oraz }\; \alpha ^{*}\alpha =\alpha ^{+}. </math></center>
-}}
-Rodzinę wyrażeń regularnych nad alfabetem  <math>{A}</math> oznaczamy symbolem <math>\mathcal{WR} </math>. Łatwo zauważyć związek pomiędzy wyrażeniami regularnymi oraz wprowadzoną wcześniej rodziną <math>\mathcal{REG}(A^{*}) </math>, regularnych języków wolnego monoidu <math>A^{*} </math>. Związek ten ustala poniższa definicja.
-{{definicja|1.3||
-'''Wartościowaniem wyrażenia regularnego''' nazywamy odwzorowanie
-<center><math>|\: \: |:\mathcal{WR}\longrightarrow \mathcal{P}(A^{*})</math></center>
-określone następująco:
-: (1) <math> \mid \emptyset \mid = \emptyset </math>
-: (2) <math>\mid a \mid = \{ a \} </math>
-: (3) <math>\mid ({\bf \alpha} + {\bf \beta})\mid = \mid {\bf \alpha} \mid \cup \mid {\bf \beta} \mid</math> <br>
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math> \mid ({\bf \alpha} {\bf \beta}) \mid = \mid {\bf \alpha} \mid \cdot \mid {\bf \beta} \mid </math><br>
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\mid {\bf \alpha}^* \mid = \mid {\bf \alpha} \mid ^*</math>
+ma w sobie liczbę najmniejszą ale nigdy nie ma największej
-}}
+</quiz>
-Odwzorowanie określające wartość wyrażenia regularnego nie jest, jak można zauważyć,
-iniekcją. Oznacza to, że różne wyrażenia regularne mogą mieć tę samą wartość, czyli określać ten sam język regularny. Prostym przykładem tego faktu  są wyrażenia regularne
-<math>a^*</math> oraz <math>(a^*)^*</math>.  Zwróćmy uwagę na wartość wyrażenia regularnego oznaczonego symbolem <math>1</math>.
-Jest mianowicie <center><math> \mid 1 \mid = \mid \emptyset^* \mid = \mid \emptyset \mid^* = \emptyset^* = \{1\} </math></center>
-Wprowadza się następującą relację równoważności w rodzinie wyrażeń regularnych.
-{{definicja|1.4||
-Wyrażenia regularne <math> {\bf \alpha} , {\bf \beta} </math> nazywamy '''równoważnymi''' i oznaczamy  <math>{\bf \alpha} = {\bf \beta} </math>, jeśli <math> \mid {\bf \alpha} \mid = \mid {\bf \beta} \mid </math>.
+<quiz>
+Zbiór  <math>S\subseteq\mathbb{N}</math>  jest taki, że jeśli  <math>s\in S</math>  to  <math>s+1\in S</math> .
+Jeśli  <math>9\in S</math> , to:
-Problem równoważności wyrażeń regularnych jest rozstrzygalny i jest PSPACE-zupełny. Wrócimy do tego problemu w kolejnych wykładach.
+<math>S=\mathbb{N}</math>
-Oto przykłady równoważnych wyrażeń regularnych
+<math>S=\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>
-<center><math>\aligned\alpha_1 + \alpha_2 & = & \alpha_2+ \alpha_1\\ (\alpha_1 + \alpha_2) +\alpha_3 & = & \alpha_1+ (\alpha_2 + \alpha_3) \\ (\alpha_1 \alpha_2) \alpha_3 & = & \alpha_1 (\alpha_2 \alpha_3) \\ (\alpha_1 + \alpha_2) \alpha_3 & = & \alpha_1\alpha_3 + \alpha_2 \alpha_3 \\ \alpha_1 ( \alpha_2 +\alpha_3) & = & \alpha_1 \alpha_2 + \alpha_1 \alpha_3 \\ (\alpha^*)^* & = & \alpha^*\\ (\alpha^*_1 \alpha^*_2)^* & = & (\alpha_1 + \alpha_2)^*\\ (\alpha^+ + 1) & = & \alpha^*  \endaligned</math></center>
+<math>S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>
-gdzie <math>\alpha ,\alpha _{1},\alpha _{2},\alpha _{3}\in \mathcal{WR} </math>.
+<math>S\supseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>
-}}
+</quiz>
-Wprost z definicji wyrażenia regularnego wynika następujaca równoważność:
-{{fakt|1.1||
-<math>L\in \mathcal{REG}(A^{*})  \Longleftrightarrow L = \mid {\bf \alpha} \mid </math> dla pewnego <math>{\bf \alpha} \in\mathcal{WR} </math>.
+<quiz>
+Zbiór  <math>S\subseteq\mathbb{N}</math>  jest taki, że jeśli  <math>a,b\in S</math> ,
+to  <math>a+b\in S</math>  oraz  <math>a+b+1\not\in S</math> .
+Jeśli  <math>0,2 \in S</math> , to:
-}}
+<math>S=\mathbb{N}</math>
-Wyrażenia regularne dają bardzo wygodne narzędzie zapisu języków należących do rodziny <math>\mathcal{REG}(A^{*})</math>.
+zbiór  <math>S</math>  zawiera wszystkie liczby naturalne, które są parzyste
-Np. język  nad alfabetem <math>\{ a,b\}</math> złożony ze wszystkich słów zaczynających się lub kończących na literę <math>{a}</math> zapisujemy jako <math>a(a+b)^* +(a+b)^*a</math>.<br> Z kolei wyrażenie regularne <math>a^+ b^+</math> oznacza język <math>L=\{a^nb^m : n,m\geq 1\}</math>.
-Dla dalszego uproszczenia zapisu przyjmiemy w naszym wykładzie następującą umowę. Jeśli język <math>L</math> jest wartością wyrażenia regularnego <math>{\alpha}</math>, czyli <math>L= \mid \alpha \mid</math>, to będziemy zapisywać ten fakt jako  <math>L= \alpha</math>. Będziemy zatem mówić w dalszym ciągu wykładu o ''języku <math>{\alpha}</math>.'' Z tych samych powodów, dla dowolnego alfabetu <math>A=\{a_1,.....,a_n\}</math> będziemy używać zapisu <math>A</math> w miejsce <math>a_1 +.....+a_n</math>.
-Zauważmy na koniec rozważań o wyrażeniach regularnych, że dość prosty w zapisie język <math>L=\{a^nb^n : n\geq 1\}</math> nie należy do rodziny <math>\mathcal{REG}(A^{*})</math> i nie można go zapisać przy pomocy wyrażeń regularnych.
+zbiór  <math>S</math>  jest zawarty w zbiorze liczb naturalnych, które są parzyste
-{{uwaga|[Dla dociekliwych]|dociek|Kończąc ten fragment wykładu poświęcony wyrażeniom regularnym warto wspomnieć o problemie "star height", czyli głębokości zagnieżdżenia gwiazdki w wyrażeniu regularnym. Mając wyrażenia regularne <math>\alpha ,\alpha _{1},\alpha _{2}\in \mathcal{WR} </math> głębokość zagnieżdżenia gwiazdki definiuje się jako liczbę <math>sh(\alpha ) </math> równą <math>0 </math>, gdy <math>\alpha  </math> jest literą z alfabetu lub zbiorem pustym, równą <math>max\{i,j\}, </math> gdy <math>\alpha =\alpha _{1}\cup \alpha _{2} </math> lub <math>\alpha =\alpha _{1}\cdot \alpha _{2} </math> i <math>sh(\alpha _{1})=i </math>, <math>sh(\alpha _{2})=j </math> oraz równą <math>i+1 </math> dla <math>\alpha =(\alpha _{1})^{*} </math>. Głębokość zagnieżdżenia gwiazdki dla języka regularnego <math>L </math> określa się jako najmniejszą liczbę <math>sh(L)=sh(\alpha ) </math>, gdzie <math>\alpha  </math> jest wyrażeniem regularnym reprezentującym język <math>L </math>. Głębokość zagnieżdżenia gwiazdki jest więc jakby miarą złożoności pętli występujących w automacie rozpoznającym język <math>L </math>. Ustalono, że dla alfabetu złożonego z jednej litery głębokość zagnieżdżenia gwiazdki jest równa co najwyżej '''1''' oraz że dla alfabetu o co najmniej dwóch literach dla dowolnej liczby <math>k\in \Bbb N </math> można wskazać język regularny <math>L </math> taki, że <math>sh(L)=k </math>. Problemem otwartym pozostaje określenie algorytmu  określającego głębokość zagnieżdżenia gwiazdki dla dowolnego języka  w klasie języków regularnych.
+zbiór  <math>S</math>  jest zbiorem wszystkich liczb naturalnych, które są parzyste
+</quiz>
-}}
-==Prawa kongruencja syntaktyczna i kongruencja syntaktyczna==
+<quiz>
+Ostatnią cyfrą liczby  <math>3^{3^n}</math>  jest:
-Opis języka regularnego za pomocą wyrażeń regularnych jest bardzo wygodny,
+zawsze  <math>3</math>
-ale nie jedyny. W kolejnych wykładach będziemy wprowadzać inne reprezentacje
-języków regularnych, takie jak automaty czy gramatyki. Pojęcia, które wprowadzimy
-teraz są również narzędziami dla opisu i badań własności języków regularnych. W
-szczególności służą do konstrukcji możliwie najprostszego automatu rozpoznającego
-dany język regularny, zwanego automatem minimalnym.
-Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. W monoidzie <math>\; A^* \;</math> wprowadzamy następujące
+zawsze  <math>3</math>  lub  <math>7</math>
-dwie relacje:
-# '''prawą kongruencję syntaktyczną'''  <math>\; P_L^r , \;</math> przyjmując<br>
+zawsze  <math>7</math>
-dla dowolnych słów <math>u, v \in A^* </math> {}<br>
-<math>u \; P_L^r \; v \;\; \mbox{ wtedy i tylko wtedy, gdy
-spełniony jest warunek}</math> <center><math> \forall w \in A^* \;\; uw \in L \; \Leftrightarrow \; vw \in L, </math></center>
-# '''kongruencję syntaktyczną'''  <math>\; P_L , \;</math> przyjmując <br>
+jakakolwiek z cyfr  <math>0,1,2,3,4,5,6,7,8,9</math>
-dla dowolnych <math>u, v \in A^* </math>{}<br>
+</quiz>
-<math>u \; P_L \; v \;\; \mbox{ wtedy i tylko wtedy, gdy spełniony jest warunek} </math> <center><math> \forall w_1, w_2 \in A^* \;\; w_1uw_2 \in L \; \Leftrightarrow \; w_1vw_2 \in L. </math></center>
-Łatwo stwierdzić, że nazwy wprowadzonych relacji pokrywają się z ich własnościami, to
-znaczy relacja <math>\; P_L^r , \;</math>
-jest rzeczywiście prawą kongruencją, a <math>\; P_L , \;</math> kongruencją.
-{{cwiczenie|[Uzupelnij]||
+<quiz>
+Jeśli <math>Z \subseteq \mathbb{N}</math>  jest jakimś zbiorem liczb naturalnych,
+który wraz z każdym początkowym fragmentem zbioru  <math>\mathbb{N}</math>
+postaci <math>\left\lbrace 0,\ldots,k-1 \right\rbrace</math> zawiera również kolejną liczbę  <math>k</math>, to wtedy
-Niech <math>A=\{ a,b\}</math> będzie alfabetem.
+zbiór  <math>Z</math>  zawiera wszystkie liczby naturalne poza skończonym podzbiorem
-# Dla języka <math>L=a^+b^+ </math> relacja
+zbiór  <math>Z</math>  zawiera wszystkie liczby naturalne
-## <math>P_L^r</math> ma <math>4</math> klasy równoważności:
+zbiór  <math>Z</math>  zawiera nieskończenie wiele liczb naturalnych
-<math>\;\;L, \;\;A^*baA^*+b^+,\;\; a^+, \;\;1</math>
-## <math>P_L</math> ma <math>5</math> klas równoważności:
+zbiór  <math>Z</math>  jest pusty
-<math>L, \;\;A^*baA^*,\;\;b^+,\;\; a^+, 1</math>
+</quiz>
-# Dla języka <math>L=\{a^nb^n : n\geq 1\}</math> obie relacje mają nieskończony indeks
-## dla <math>P_L^r</math>  klasami równoważności są zbiory <br>
+<quiz>
-<math>L_i =\{a^nb^{n-i} : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}_0</math>, <math>A^* \setminus\bigcup_{i=0}^\infty L_i</math>
+Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?
-## dla <math>P_L</math>  klasami równoważności są zbiory <br>
+klasa na pewno się nie pogodzi
-<math>L_i =\{a^nb^{n-i} : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}_0</math>,<br>
-<math>L'_i =\{a^{n-i}b^n : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}</math> <br>
-<math>A^* \setminus[\bigcup_{i=1}^\infty (L_i\cup L'_i )\cup L_0 ]</math>
-}}
+klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia
-Udowodnimy następujące własności relacji <math>\; P_L^r \;</math> oraz <math>\; P_L \;</math>.
+jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić
-Prawa kongruencja syntaktyczna <math>\; P_L^r \;</math> jest największą w sensie inkluzji spośród wszystkich
+jeżeli w klasie byłyby już co najmniej dwie osoby,
-prawych kongruencji <math>\rho  </math> takich, że <center><math>L = \bigcup_{w\in L}[w]_\rho </math></center>
+przy czym osoby w klasie byłyby ze sobą pogodzone,
-Kongruencja syntaktyczna <math>\; P_L \;</math> jest największą w sensie inkluzji spośród wszystkich
+to reszta klasy miałaby szansę się pogodzić
-kongruencji <math>\rho  </math> takich, że <center><math>L = \bigcup_{w\in L}[w]_\rho </math></center>
+</quiz>
-Dowód przeprowadzimy dla prawej kongruencji syntaktycznej. Uzasadnienie tezy dla
-kongruencji <math>\; P_L \;</math> przebiega podobnie.
+<quiz>
-Niech  <math>\;\rho \;</math> będzie dowolną prawą kongruencją spełniającą założenia i
+Jeśli  <math>S\subseteq\mathbb{N}</math> , to:
-niech <math>u\rho v </math>. Zatem dla każdego <math>w\in A^{*} </math> jest
+zbiór  <math>S</math>  ma element największy
-<center><math>uw\rho vw \Rightarrow (uw\in L\Leftrightarrow vw\in L) \Leftrightarrow u\; P_L^r \; v. </math></center>
+zbiór  <math>S</math>  ma element najmniejszy
-W konsekwencji <math>\rho \subseteq P_L^r.</math> W
-szczególności więc dla dowolnego <math> u \in A^*</math> ma miejsce inkluzja <math>[u]_\rho \; \subseteq \; [u]_{P_L^r}.</math> Zatem <math>L\subset \bigcup _{w\in L}[w]_{P^{r}_{L}} </math>.
+zbiór  <math>S</math>  ma element największy, o ile  <math>S</math>  jest niepusty
-Aby udowodnić inkluzję w stronę przeciwną ustalmy dowolne <math>\; u \in L \;</math> i niech <math>v \in [u]_{P_L^r}.</math>
-Przyjmując <math>\; w =1 \;</math> w definicji&nbsp;[[##d1|Uzupelnic d1|]] relacji <math>\; {P_L^r} \;</math>  otrzymamy równoważność
+zbiór  <math>S</math>  ma element najmniejszy, o ile  <math>S</math>  jest niepusty
-<math>\; u \in L \; \Leftrightarrow \; v \in L \;.</math> A więc <math>\; v \in L \;.</math><br>
+</quiz>
-<math>\diamondsuit</math>
-Jeśli język <math>L </math> jest regularny, to  relacja <math>\; P_L^r \;</math> jest największą
-w sensie inkluzji spośród wszystkich
-prawych kongruencji takich, że język <math>L</math> jest sumą jej pewnych klas równoważnosci
-a relacja <math>\; P_L \;</math> jest
-największą w sensie inkluzji
-spośród wszystkich kongruencji spełniających analogiczny warunek.
-Obie relacje mają skończony indeks, czyli dzielą wolny monoid <math>A^*</math> na
-skończoną liczbę klas równoważności.
----- dla dociekliwych - start ----
-Pojęcie, które wprowadzimy teraz - monoid syntaktyczny języka -  wiąże teorię
-języków formalnych, a
-w szczególności teorię języków rozpoznawalnych, z&nbsp;teorią półgrup. Związek ten
-stanowi podstawę dla bardziej zaawansowanych
-problemów teorii języków i automatów wykraczających poza ramy tego wykładu.
-Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. '''Monoidem syntaktycznym'''
-języka <math>\; L \;</math> nazywamy strukturę ilorazową
-<center><math>M(L) = A^*/P_L .</math></center>
-Dualnie, tworząc iloraz <math>S(L) = A^+/P_L</math> wprowadza się pojęcie półgrupy syntaktycznej
-języka <math>\; L \;</math>. Oba wprowadzone tu pojęcia zilustrowane bedą w trakcie dalszych
-rozważań.
----- dla dociekliwych - end ----
-==AUTOMAT MINIMALNY==
-Określenie języka rozpoznawalnego postuluje istnienie automatu o skończonej
-liczbie stanów działającego w odpowiedni sposób. Należałoby zatem wskazać algorytm
-budowy takiego automatu dla języka rozpoznawalnego. Oczywiście interesuje nas algorytm
-prowadzący do automatu o możliwie najprostszej postaci.  Najprostsza postać, w tym kontekście,
-oznacza najmniejszą liczbę stanów.
-Automat <math>\mathcal{A} </math></center><nowiki>=</nowiki> (S,A,f,s_0,T) <math> rozpoznający język </math>L<math>
-na\-zy\-wa\-my \textbf{automatem minimalnym}\index{automat minimalny},
-jeśli posiada najmniejszą licz\-bę stanów spośród wszystkich automatów
-rozpoznają\-cych język </math> L. <math>
-\enddefin
-Kwestią istnienia takiego automatu minimalnego zajmujemy się teraz. W kolejnym
-wykładzie przedstawimy algorytmy konstrukcji automatu minimalnego.
-W poniższym twierdzeniu występuje automat ilorazowy </math>{A}_{P^{r}_{L}} <math>
-określony przez
-prawą kongruencję </math>P_L^r<math>.
-\begintheor
-Dla dowolnego automatu </math>{A} <center><math>= (S,A,f,s_0,T) \;</math> rozpoznającego
-język <math>\; L \subset A^* \;</math> istnieje jedyny
-epimorfizm <math>\varphi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
-taki, że <math>\varphi (s_{0})=[1]_{P^{r}_{L}}. </math>
-Prawa kongruencja automatowa <math>\sim _{\mathcal{A}} </math> ma
-skończony indeks
-i <math>L=\bigcup _{u\in L}[u]_{\sim _{\mathcal{A}}} </math>.
-Zatem z twierdzenia&nbsp;[[##trr2|Uzupelnic trr2|]] wynika, że
-<center><math>\sim _{\mathcal{A}}\subseteq P^{r}_{L}=\sim _{\mathcal{A}_{P^{r}_{L}}}.</math></center>
-Istnienie epimorfizmu <math>\; \varphi \;</math> wynika z  twierdzenia 1.1, wykład 3.
-Epimorfizm ten określony jest dla dowolnego stanu <math>s\in S </math>
-równością <math> \varphi(s) = f^*([1]_{P_L^r},w) = [w]_{P_L^r},</math> gdzie <math>w </math> jest
-słowem takim, że <math>f(s_0,w)=s</math>.
-Jest to jedyny epimorfizm spełniający warunki tezy dowodzonego
-twierdzenia. Dla każdego epimorfizmu  <math>\; \psi \;</math> takiego,
-że <math>\psi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
-i <math>\psi (s_{0})=[1]_{P^{r}_{L}} </math>
-mamy<br> <math>\;\forall s \in S</math> <center><math>\psi(s) = \psi(f(s_o,w)) = f^* (\psi(s_0),w) = f^* ([1]_{P_L^r},w) = [w]_{P_L^r},</math></center>
-gdzie <math> f(s_0,w) = s .</math>
-Tak więc <math>\; \psi = \varphi .\;\diamondsuit</math>
-Zatem udowodnione twierdzenie zapewnia nas o istnieniu automatu minimalnego, co
-formułujemy w następującym wniosku.
-Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. Automat
-<center><math>\mathcal{A}_{P^{r}_{L}}=\left( A^{*}/_{P^{r}_{L}},A,f^{*},[1]_{P^{r}_{L}},T\right), </math></center>
-gdzie <math>\; T = \{ [w]_{P_L^r} \; : \; w \in L \}, \;</math> jest automatem
-minimalnym rozpoznającym język <math>\; L \;</math>. Oznaczać go
-będziemy symbolem <math>\mathcal{A}_{L} </math>.
----- dla dociekliwych - start ----
-Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i
-podaje kolejny warunek równoważny na to,
-żeby język <math>L</math> był rozpoznawany przez automat.
-Niech <math>L\subset A^{*} </math> będzie dowolnym językiem.{}{}
-. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest
-izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
-<center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
-{}{}
-. (tw. J.Myhill'a) Język <math>\; L \subset A^* \;</math> jest rozpoznawalny wtedy i tylko wtedy,
-gdy <math>\; M(L) \;</math> jest monoidem skończonym.
-Dla dowodu punktu 1, wykażemy, że
-<center><math>P_{L}=Ker_{\tau _{\mathcal{A}_{L}}}, </math></center>
-gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </math>
-<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
-<center><math>\begin{array} {c}
-(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
-\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
-[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
-\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
-\Leftrightarrow (u,v) \in P_L\\
-\end{array} </math></center>
-Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
-ma postać:  <br>
-RYSUNEK ja-lekcja4-w-rys1.pdf<br>
-czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
-Dla dowodu punktu 2 załóżmy, że język <math>\; L \;</math> jest rozpoznawalny.
-Zatem
-<center><math>L = \bigcup_{w \in L} [w]_\rho ,</math></center> gdzie <math>\; \rho \;</math> jest kongruencją o skończonym indeksie.
-Z twierdzenia&nbsp;[[##trr2|Uzupelnic trr2|]] wnioskujemy, że <math>\rho \subseteq P_L .</math> Oznacza to, że indeks relacji <math>\; P_L \;</math> jest
-niewiększy od indeksu <math>\; \rho, \;</math> a co za tym idzie, <math>\; M(L) = A^*/P_L \;</math> jest monoidem skończonym.
-Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm kanoniczny <center><math>k : A^* \longrightarrow A^*/P_L = M(L).</math></center>
-Pokażemy, że spełnia on warunki z punktu 4 twierdzenia 1.2 z wykładu 3.  <math>M(L) \;</math> jest skończony, więc pozostaje do wykazania
-równość
-<center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
-<math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
-<center><math>\begin{array} {c}
-v \in k^{-1}(k(L))\Rightarrow k(v) \in k(L)\Rightarrow\exists u \in L:k(v) = k(u) \in k(L)\Leftrightarrow\\
-\Leftrightarrow \exists u \in L:[v]_{P_L} = [u]_{P_L}\Leftrightarrow\exists u \in L:v \in L\Leftrightarrow u\in L.\\
-\end{array}
-</math></center>
-Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>.
-<math>\diamondsuit</math>
----- dla dociekliwych - end ----
-Z twierdzenia [[##3.1|Uzupelnic 3.1|]] wynika, że określenie klas abstrakcji prawej kongruencji syntaktycznej
-<math>P^r_L</math> prowadzi do  określenia  minimalnego automatu rozpoznającego  język <math>L</math>.
-Prezentowane poniżej twierdzenia wskazują sposób konstrukcji prawej kongruencji syntaktycznej
-dla języka <math>L </math>.
-Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, <br> a  <math>\; \Theta_L \subset A^* \times A^* \;</math>  relacją
-równoważności o  dwóch klasach równoważności <math>L</math> i <math> A^* \setminus L</math>.
-Przez <math>\; \rho_i \;</math> dla <math>\; i \in {\Bbb N} </math> oznaczmy zstępujący ciąg relacji określony następująco:
-<math>\rho_1 = \Theta_L ,\;\;</math> a dla <math>\; i = 2,... </math> przyjmijmy
-<math>\rho_i = \{ (u,w) \in \; A^* \times A^* \; : \; (ua,wa) \in \; \rho_{i-1} \;\;\; \forall a \in A \cup \{1\}\}.</math>
-{ Wtedy <math>\;\; \bigcap \rho_i = P_L^r \;\;</math>. }
-Na początku uzasadnimy, że <math>\; \bigcap \rho_i \;</math> jest prawą kongruencją na <math>\; A^*</math>.
-Załóżmy więc, że słowa <math>\; x , y \in A^* \;</math> są w relacji <math>x \; \bigcap \rho_i \;y \;</math>.
-Wybierzmy
-dowolne słowo <math>z\in A^{*} </math>
-i niech <math>k </math> oznacza długość tego słowa. Z&nbsp;założenia
-wynika, iż <math>x\, \rho _{i+k}\, y </math>, co w świetle definicji ciągu
-relacji <math>\rho _{i} </math> implikuje, że <math>xz\: \rho _{i}\: yz. </math> Ponieważ
-<math>i </math> jest dowolne wnioskujemy ostatecznie, że  <math>xz \; \bigcap \rho_i \; yz \;,</math>
-co kończy dowód faktu, że <math>\; \bigcap \rho_i \;</math> jest prawą kongruencją.
-Dowiedziemy teraz równości <center><math>\bigcap \rho_i \; = \; P_L^r .</math></center>
-Dla uzasadnienia inkluzji <math>\bigcap \rho_i \;\subseteq\; P_L^r</math> zauważmy, że
-jeśli <math>x \; \bigcap \rho_i \; y ,</math> to dla dowolnego <math>z\in A^{*} </math> mamy
-<math>xz \; \bigcap \rho_i \; yz</math>, a w szczególności <math>xz \; \rho_1 \; yz.</math>
-Z definicji relacji <math>\rho _{1} </math> dla dowolnego <math>z\in A^{*} </math> prawdziwa
-jest równoważność <center><math>xz \in L \;\; \Leftrightarrow \;\; yz \in L.</math></center>
-A więc <math>x \;\; P_L^r \;\; y </math>. Inkluzję w stronę przeciwną pokażemy, dowodząc indukcyjnie
-ze względu na <math>i=1,2,... </math> , że dla dowolnych <math>\;x , y \in A^* \;</math> prawdziwa
-jest następująca implikacja
-<center><math>x \;\; P_L^r \;\; y \;\;\; \Longrightarrow \;\;\; x \; \rho_i \; y \;\;.</math></center>
-Załóżmy zatem, że <math>x \;\; P_L^r \;\; y. </math>
-Z definicji  <math>\; P_L^r \;</math> wynika, że dla dowolnego <math>z \in A^* </math> prawdziwa jest równoważność
-<center><math> xz \in L \;\; \Leftrightarrow \;\; yz \in L.</math></center> Przyjmując <math>\; z=1 \;</math> otrzymujemy
-żądaną własność dla <math>\rho _{1}. </math> Załóżmy teraz, że
-prawdziwa jest implikacja
-<center><math>x \;\; P_L^r \;\; y \;\;\; \Longrightarrow \;\; x \; \rho_i \; y.</math></center>
-dla <math>i = 1,...,n-1</math> oraz dla dowolnych <math>x , y \in A^*.</math>
-Stąd,
-że <math>P_L^r</math> jest prawą kongruencją, wnioskujemy, że dla dowolnego <math>\; a \in A \cup \{1\} \;</math>
-spełniona jest relacja <math>xa \;\; P_L^r \;\; ya .</math>
-Korzystając z założenia indukcyjnego mamy
-<math>xa \;\; \rho_{n-1} \;\; ya</math> dla dowolnego <math>\; a \in A \cup \{1\} \;</math>.
-A to oznacza z definicji <math>\; \rho_i \;</math>, że <math>x \;\; \rho_n \;\;y </math> i kończy dowód.
-<math>\diamondsuit</math>
-Kolejne twierdzenie charakteryzuje relację <math>P^r_L</math> dla języka   rozpoznawalnego i orzeka, iż
-w przypadku języka rozpoznawalnego ciąg relacji <math>\rho_i</math>, aproksymujacych  <math>P^r_L</math>, jest
-skończony.  Równoważność dwóch pierwszych warunków poniższego twierdzenia nazywana bywa często
-w literaturze twierdzeniem A.Nerode.
-Następujące warunki są równoważne:
-# Język <math>L</math> jest rozpoznawalny
-#  Relacja <math>P^r_L</math> ma skończony indeks
-#  Ciąg relacji <math>\rho_i</math> stabilizuje się, co oznacza, że istnieje <math>i\in {\Bbb N} </math> takie, że <center><math>\rho_i = \rho_{i+1}=....</math></center>Dla najmniejszego takiego <math>i</math> prawdziwa jest równość <math>\rho_i = P^r_L.</math>
-Dowód poprowadzimy według następujacego schematu:
-{ [[##u1|Uzupelnic u1|]] <math>\Longleftrightarrow  </math> [[##u2|Uzupelnic u2|]]<math>\Longleftrightarrow  </math>[[##u3|Uzupelnic u3|]] }
-[[##u1|Uzupelnic u1|]] <math>\Longrightarrow </math> [[##u2|Uzupelnic u2|]]
-{ <math>P^r_L</math> jest największą w sensie inkluzji relacją spełniająca
-warunki punktu 2 z&nbsp;twierdzenia 1.2, wykład 3. Z tego samego twierdzenia wynika
-skończoność indeksu. }
-[[##u1|Uzupelnic u1|]]<math>\Longleftarrow </math> [[##u2|Uzupelnic u2|]]
-Relacja <math>P^r_L</math> jest prawą kongruencją, ma skończony indeks oraz
-<center><math>L = \bigcup_{w \in L}[w]_{P^r_L}.</math></center> Z twierdzenia z&nbsp;twierdzenia 1.2, wykład 3 wynika więc, że język <math>L</math> jest rozpoznawalny.
-[[##u2|Uzupelnic u2|]]<math>\Longrightarrow </math> [[##u3|Uzupelnic u3|]]
-Dowód poprowadzimy nie wprost. Załóżmy więc, że dla każdego <math>i\in {\Bbb N} </math>
-jest <math>\rho_i \neq \rho_{i+1}.</math> Oznacza to, że dla każdego <math>i\in {\Bbb N} </math>
-indeksy relacji <math>\rho _{i} </math>  tworzą ciąg silnie rosnący, to znaczy
-spełniają zależność <math>ind\rho_i < ind\rho_{i+1}.</math> Ponieważ <math>ind\rho_1 = 2,</math> to dla każdego <math>i\in {\Bbb N} </math>
-prawdziwa jest nierówność <math>ind\rho_i > i.</math> A&nbsp;to prowadzi do wniosku, że dla dowolnego <math>i\in {\Bbb N} </math>
-<center><math>indP^r_L = ind\bigcap\rho_i >i .</math></center> Zatem indeks relacji <math>P^r_L</math> jest nieskończony, co jest sprzeczne z założeniem.
-[[##u2|Uzupelnic u2|]] <math>\Longleftarrow </math> [[##u3|Uzupelnic u3|]]
-Udowodnimy indukcyjnie ze względu na <math>j</math>, że każda z relacji <math>\rho_j</math> dla <math>j=1,...,i</math>
-ma skończony indeks. Oczywiście <math>ind\rho_1 = 2.</math> Załóżmy teraz, że relacja <math>\rho_j</math>
-ma skończony indeks. Z definicji relacji <math>\rho_{j+1}</math> wynika,
-że jej klasy równoważności powstają przez podział
-klas równoważności <math>[w]_{\rho_j}</math> na skończoną liczbę klas relacji <math>\rho_{j+1}</math>
-(skończona jest
-liczba możliwych do spełnienia warunków prowadzących do podziału). Oznacza to, że
-indeks relacji <math>\rho_{j+1}</math> jest również skończony, a więc
-relacja <math>P^r_L</math> ma również skończony indeks.
-<math>\diamondsuit</math>
-Wykorzystamy powyżej udowodnione własności do konstrukcji automatu minimalnego rozpoznającego
-język <math>L</math>. Warto zauważyc, iż punktem wyjścia dla tej konstrukcji jest język <math>L</math> zadany, na
-przykład, poprzez wyrażenie regularne.
-{{cwiczenie|[Uzupelnij]||
-Niech do języka <math>L</math> należą wszystkie słowa nad alfabetem <math>A=\{a,b\}^* </math> zaczynające się lub kończące literą <math>a</math>.
-Skonstruujemy minimalny automat akceptujący język <math>L</math>.
-; <math>\rho _{1}</math>
-:   <math>L=aA^* +A^* a,\;\; A^{*}\setminus L =bA^*b +b+1</math>
-; <math>\rho _{2}</math>
-:  <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b+1,</math>
-; <math>\rho _{3}</math>
-:  <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b, \;\;1,</math>
-Ponieważ  <math>\rho _{3}=\rho _{4}</math>, to <math>P^r_L=\rho _{3}</math> i automat minimalny ma <math>4</math> stany.<br>
-Przyjmujemy <math>s_0 =[1]</math>, <math>s_1=bA^*a </math>, <math>s_2=aA^*a+a </math>, <math>s_3=bA^*b +b</math>
-oraz <math>T=\{s_1,s_2\} </math>, a automat minimalny <math>\mathcal{A}_{L}=\left( A^{*}/_{\rho _{3}},f^{*},s_{0},T\right)  </math>
-przedstawiony jest przy pomocy grafu:
-RYSUNEK ja-lekcja4-w-rys2.JPG
-}}
-{{cwiczenie|[Uzupelnij]||
-Dla języka <math>L=\left\{ w \in \{ a,b\}^* :\#_a w =2k, \#_b w =2l+1
-,\; k,l\geq 0  \right\}  </math> określimy ciąg relacji <math>{\rho}_i</math>, a
-następnie relację <math>P^{r}_{L} </math>. Umożliwi nam to, w świetle
-powyższych rozważań, zbudowanie automatu minimalnego rozpoznającego
-ten język. Poniżej wypisane są klasy równoważności relacji <math>\rho _{1} </math> oraz <math>\rho _{2} </math>, <math>\rho _{3}=\rho _{2} </math>, co
-kończy proces obliczania relacji <math>\rho _{i} </math> i daje równość <math>\rho _{2}=P^{r}_{L} </math>.<br>
-; <math>\rho _{1}</math>
-:   <math>L, A^{*}\setminus L</math>
-; <math>\rho _{2}</math>
-:  <math>L, L_1, L_2, L_3</math>, gdzie<br>
-<math>L_1=\left\{ w \in \{ a,b\}^* :\#_a w =2k, \#_b w= 2l, \; k,l\geq 0  \right\},</math><br>
-<math>L_2\left\{ w \in \{ a,b\}^* :\#_a w =2k+1, \#_b w= 2l+1, \; k,l\geq 0  \right\},</math><br>
-<math>L_3=\left\{ w \in \{ a,b\}^* :\#_a w =2k+1, \#_b w= 2l, \; k,l\geq 0  \right\},</math>
-Przyjmując <math>s_0 =L_1=[1]</math>, <math>s_1=L_3</math>, <math>s_2=L_2</math>, <math>s_3=L</math> oraz <math>T=\{s_3\} </math>
-automat minimalny <math>\mathcal{A}_{L}=\left( A^{*}/_{\rho _{2}},f^{*},s_{0},T\right)  </math>
-przedstawiony jest przy pomocy grafu:
-RYSUNEK ja-lekcja4-w-rys3.JPG<br>
-}}
----- dla dociekliwych - start ----
-Powyższe twierdzenia podają również sposób konstrukcji
-monoidu syntaktycznego języka <math>L</math>.
----- dla dociekliwych - end ----