ماشین های تورینگ، تشخیص پذیری و تصمیم پذیری زبان ها

ماشین های تورینگ، تشخیص پذیری و تصمیم پذیری زبان ها

اسلاید 1: ماشین های تورینگ، تشخیص پذیری و تصمیم پذیری زبان هاجلسات حل تمرین نظریه زبان ها و ماشین هادانشگاه صنعتی شریفبهار 87

اسلاید 2: EnumeratorsShow that a language is decidable iff some enumerator enumerates the language in lexicographic order.Show that every infinite recognizable language has an infinite decidable language as a subset.

اسلاید 3: طراحی تصمیم گیر

اسلاید 4: زبان های مکمل-تشخیص پذیر(co-recognizable)

اسلاید 5: زبان های تصمیم پذیر

اسلاید 6: زبان های تصمیم پذیرM is a Turing machineDoes M take more than k steps on input x?Does M take more than k steps on some input?Does M take more than k steps on all inputs?Does M ever move the tape head more than k cells away from the starting position?

اسلاید 7: زبان های تصمیم پذیر{M: M is the description of a Turing machine and L(M) is a Turing recognizable language}

اسلاید 8: زبان های تصمیم ناپذیر

اسلاید 9: زبان های تشخیص ناپذیر

اسلاید 10: زبان های تشخیص ناپذیرConsider the following language L:  L = { <M> | for every input string w, M will halt within 1000|w|2 steps } Show that this language is not recognizable. (Reduce from ~ATM.)complement of

اسلاید 11: طراحی تشخیص دهنده

اسلاید 12: Close look to the formal definition of a TM Exercise 3.5:Can a Turing machine ever write the blank symbol on its tape?Can the tape alphabet be the same as the input alphabet?Can a Turing machines read head ever be in the same location in two successive steps?Can a Turing machine contain just a single state?

اسلاید 13: خواص بسته بودن زبان های تشخیص پذیر: اجتماع اشتراک تکرار(*) الحاق زبان های تصمیم پذیر اجتماع اشتراک مکمل گیری تکرار(*) الحاق

اسلاید 14: Robustness doubly infinite tape k-stack PDAs (k>1) A Turing machine with only RIGHT and RESET moves Cyclical Turing machine A queue automaton 2(k) head Turing machine Turing machine with k-dimensional tape A single tape TM not allowed to change the input -> regular language Only Right and Stay Put moves -> regular language

اسلاید 15: Clue to the Solution: input-read-only TMAt most the last |Q| squares of input on tape can be determining.Myhill-Nerode theoremif a language L partitions ∑* into a finite number of equivalence classes then L is regular.See:http://www.eecs.berkeley.edu/~tah/172/7.pdfhttp://en.wikipedia.org/wiki/Myhill-Nerode_theorem