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.
0
0
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.
0
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
0
o_O język pusty to nie znaczy język który zawiera epsilon tylko język który nie zawiera żadnych elementów.
0
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?
0
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.
0
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)?
0
Dziękuję.
0
Język miałem poprawny, wykładowca mi to uznał, nie dostałem punktów za uzasadnienie.
0
Zakładając że byłoby tam n>=0, to udałoby się ułożyć jakieś sensowne uzasadnienie ?
2
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
0
Ok, dziękuję za pomoc :)