Έστω η γλώσσα:
EQ= {(M, Π)| η μηχανή Turing Μ και το πεπερασμένο αυτόματο Π αναγνωρίζουν
την ίδια γλώσσα, δλδ, L(M)= L(Π)}.
Αποδείξτε ότι η EQ είναι μη αποφασίσιμη. Να κάνετε την αναγωγή από τη μη
αποφασίσιμη γλώσσα: HALT = {(M,w)| η μηχανή Turing M τερματίζει με είσοδο w}.
0 Σχόλια