Witam, mam zadanie z przedmiotu automaty i języki formalne: znaleźć taki język L (niepusty) dla którego zachodzi L2=L4, oraz uzasadnij. Otóż taki język znalazłem, jest to L={an:n>0} lecz jak to sensownie udowodnić? Sam opis że język nieskończony do potęgi jest nadal językiem nieskończonym nie wystarczy.
Nie wiem co uzasadnienie że język nieskończony do potęgi jest językiem nieskończonym miałoby tutaj niby dać.
Przykład:
L = {an : n>1} -> L2 zawiera aaaa a L^4 już nie, a oba są nieskończone.
Zresztą twój przykład języka jest niepoprawny bo język L2 zawiera aa a język L4 już nie. Potrzebowałbyś w tym zbiorze mieć epsilon żeby to zadziałało.
Jak już napisałem w treści, język nie może być pusty, czyli składać się z epsilona, sądzę że tu trzeba użyć domknięcia Kleenie'go ale nie wiem jak
o_O język pusty to nie znaczy język który zawiera epsilon tylko język który nie zawiera żadnych elementów.
Uczę się programowania i ogólnie rzeczy "około-IT", ale nie studiuję Informatyki, lecz Elektronikę. Nie mamy takich rzeczy jak języki-automaty. Czy to się przydaje do czegoś czy nie zaprzątać sobie tym głowy?
Automaty mogą się przydać w kontekście maszyn stanów za pomoca których czasami sie coś modeluje.
Na pewno warto wiedzieć co to są języki regularne i jak się używa wyrażeń regularnych.
Poza tym to jest taki must-have jeśli chcesz się bawić w pisanie kompilatora jakiegoś języka, bo wtedy będziesz potrzebował parser i lekser a do tego potrzeba ci zwykle bezkontekstowej gramatyki języka.
Dzięki za odpowiedź, czyli się przyda, bo chciałem kiedyś napisać jakiś "prosty" kompilator. Generalnie była mowa o automatach skończonych Mealy'ego i Moore'a. Jest jakaś przystępna literatura na ten temat (automaty, języki formalne)?
Dziękuję.
Język miałem poprawny, wykładowca mi to uznał, nie dostałem punktów za uzasadnienie.
Zakładając że byłoby tam n>=0, to udałoby się ułożyć jakieś sensowne uzasadnienie ?
Jakbyś miał tam n>=0 to byloby to przynajmniej poprawne ;] A uzasadnienie też by się znalazło:
L2 zawiera wszystkie elementy języka L w podwojonej formie, L4 w formie poczwórnej. W praktyce oznacza to że L2 miałby tylko słowa o parzystej długości od 2 do nieskończoności z krokiem 2, a L4 miałby tylko słowa o parzystej długości od 4 do nieskończoności z krokiem 4. Językowi L4 brakuje słów postaci aanaa dla n>1. Jedyny sposób na uzyskanie takich słów z wyrażeń postaci xyzvn to podstawienie za dwa symbole epsilona.
Jeśli język L zawiera epsilon to język L2 = {(a|eps)n : n=2k i k>=0}
a język
L4={(a|eps)n : n=4k i k>=0} = {((a|eps)(a|eps))n : n=2k i k>=0} = {((a|eps)a)n : n=2k i k>=0} U {((a|eps)eps)n : n=2k i k>=0} = {((a|eps)a)n : n=2k i k>=0} U {(a|eps)n : n=2k i k>=0} = {((a|eps)a)n : n=2k i k>=0} U L2 = {(eps a)n : n=2k i k>=0} U {(aa)n : n=2k i k>=0} U L2 = {(a)n : n=2k i k>=0} U {(aa)n : n=2k i k>=0} U L2 = L2
bo:
{(a)n : n=2k i k>=0} zawiera się w {(a|eps)n : n=2k i k>=0} czyli zawiera się w L2 więc {(a)n : n=2k i k>=0} U L2 = L2
{(aa)n : n=2k i k>=0} zawiera się w {(a|eps)n : n=2k i k>=0} czyli zawiera się w L2 więc {(aa)n : n=2k i k>=0} U L2 = L2
Ok, dziękuję za pomoc :)