مرجع دانلود پاورپوینت های درسی

حجم فایل : 132.0 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 17
بنام خدا ماشین های تورینگ، تشخیص پذیری و تصمیم پذیری زبان ها Enumerators Show 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. طراحی تصمیم گیر زبان های مکمل-تشخیص پذیر(co-recognizable) زبان های تصمیم پذیر زبان های تصمیم پذیر M is a Turing machine

Does 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?
زبان های تصمیم پذیر {M: M is the description of a Turing machine and L(M) is a Turing recognizable language}
زبان های تصمیم ناپذیر زبان های تشخیص ناپذیر زبان های تشخیص ناپذیر Consider the following language L:
 
L = { | 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 طراحی تشخیص دهنده 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?


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

زبان های تصمیم پذیر
اجتماع
اشتراک
مکمل گیری
تکرار(*)
الحاق
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 Clue to the Solution: input-read-only TM At most the last |Q| squares of input on tape can be determining.

Myhill-Nerode theorem
if a language L partitions ∑* into a finite number of equivalence classes then L is regular.



See:
http://www.eecs.berkeley.edu/~tah/172/7.pdf
http://en.wikipedia.org/wiki/Myhill-Nerode_theorem پایان...