4 - Decision problems and languages

• decision problem

  yes/no question
• reverse operation R

  upon reversing, every symbol we add on the left must move to the very right
• binary palindrome -decision problem


  $x^R =$$x$
• language over an alphabet is a collection of string over a set of strings
• boolean function

  A) 1

  
• binary language

  A) palindrome

  B) x^R

  
• A language A is regular if there exists a DFA M such that A = L(M)
• Regular operations

  A) union

  B) concatenation

  C) star

  
• Pumping lemma

  A) regular

  B) natural

  C) pumping length

  D) three

  E) central

  F) non-empty

  G) first two

  
• palindrome is not a regular language
• TMs can process input string of arbitrary length. And they do this in a dynamic (back and forth) and active (back-forward) fashion
• Decidable langague :

  1. M accepts every string within the language
  2. M reject every string not contained in the language
• Every regular language is also a decidable language
• Palindrome is a decidable langauge
• Turing machines are strictly more powerfull than DFAs
• Serieus drawback of TM : they may not stop and loop on forever
• semidecidable

  
• interpreters can be troublesome

  
  

  interpreter is a program which takes as

  • program (M) + input (w )
  • simulates M on input w.
• semidecidable == completely enumerable
• Membership illustration among language classes

  A) reg

  B) dec

  C) s-dec

  D) all

  E) parity

  F) accept

  G) palindrome

  
• Church-Turing thesis

  Any function that can be computed by a mechanical/physical process can also be computed by a Turing machine