Witam. Mam problem z takim zadaniem:
Dany jest automat M, N oraz K:
Podaj automat deterministyczny R taki, że L(R) = L(M) U L(N) U L(K)
Próbowałem na kilka sposobów ale dalej nie wiem jak zrobić z tego sumę i to automatem deterministycznym ?
0
1
Najpierw wyznacz sobie jezyki akceptowany przez te automaty, zrób sumę tych jęzków a potem zaprojektuj automat który są sume akceptuje.
Niemniej juz na pierwszy rzut oka widać że połączenie M z N jest trywialne, ot wystarczy do M dodać przejscie ze stanu 2 przez "a" do stanu 2 i oznaczyć 2 jako stan akceptujący.
Analogicznie połączenie tego dalej z automatem K jest trywialne - ot wystarczy oznaczyć w automatcie M stan 3 jako akceptujacy i dodać brakujące przejście ze stanu 1 do 4 przez "b" oraz z 4 do 3 przez "a" (tak jak w automacie K).
1
Dla mnie to powinno wyglądać tak:
0
Jeżeli dodam przejście z 1 do 4 to wtedy automat nie będzie już deterministyczny (z 1 będzie można iść do 2 albo do 4).
0
@winerfresh - po co potrzebne ci jest przejście ze stanu 2 do 3 ? Nie można by zrobić pętli na "a" przy 2 ?
1
@kucyk1 nie, gdyż wtedy automat akceptował by więcej ciągów niż oryginały, np. aaaaab.