Czy podany język jest rekurencyjny?

lunex
Użytkownik
Użytkownik
Posty: 63
Rejestracja: 1 cze 2006, o 15:13
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy

Czy podany język jest rekurencyjny?

Post autor: lunex » 19 cze 2011, o 16:56

G1, G2 i G3 są pewnymi wyrażeniami regularnymi. Czy język:
K6 = { (<G1>,<G2>,<G3>); L(G1) L(G2) = L(G3)}
jest rekurencyjny? Jeżeli odpowiedź jest pozytywna opisz algorytm.
Czy mógłby ktoś rozwiązać to zadanie?

Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

Czy podany język jest rekurencyjny?

Post autor: paladin » 21 cze 2011, o 10:21

Potrzebne są dwa kroki:

- konstrukcja wyrażenia regularnego G4, które będzie odpowiadało językowi L(G1)/L(G2),
- sprawdzenie, czy L(G3) = L(G4).

Oba kroki są już bardzo typowe, powinieneś je mieć w notatkach

ODPOWIEDZ