Part 1: Automata and Languages

Chapter 1: Regular Languages

ITEC 420 - Section 1.4 - Non-Regular Languages

TM Parts

• FSM and Tape (Infinite in 1 direction)


• $\Sigma \subset\ \Gamma$


• $\textrm{ blank } \in \Gamma, \textrm{ blank } \notin \Sigma$


• Transition: Read, Write, Move (L/R), state
• Move Left on Left end of tape leaves head on left end
• Unique accept state, unique reject state

Computation

• Tape initially has Input string on left end, rest of tape has blanks


• Computation begins with read head at left of tape


• Computation ends if accept or reject state is entered


• Computation can loop

Accepting/Recognizing a String

• $M$ accepts $w$ if $w$ determines a computation from the initial state to the accept state


• $M$ does NOT accept a string if the computation on w
• Enters the reject state (halting the machine)
• Loops

Looping

• Notice that the TM is deterministic and it loops


• NFA and NPDA can loop, but
• DFA and DPDA can not loop

Do More Tapes Give More Power?

• No: A single tape machine can simulate a mutitape machine
• How: Encode multiple tapes on a single tape
• Example: Encode Tapes 1 and 2 onto Tape 3
• Assume machine M1 has tape T1
• Assume machine M2 has two tapes T2 and T3(and two read heads)
• Transitions Read/Write pairs of symbols, and move a pair of directions


• Simulate M2 on Machine M1 (with tape T1)


• Example: Tape 2: 123 (head on 2) and Tape 3: abc (head on c)
• Use a special symbol (eg #) to separate tapes on T1: 123#abc
• Use dotted symbols to mark tape head: dotted 2 and c above
• Rewrite transitions to update dotted symbols, etc

Does Nondeterminism Give Extra Power?

• No: A DTM can simulate a NTM
• How: Use 3 tapes to simulate all possible computations (until accept/reject):
1. Tape 1: copy of input string
2. Tape 2: used to execute current computation
• Step 1: copy input string from tape 1
• Step 2: execute branches of computation as shown on tape 3
3. Tape 3: Lists branches taken in all computations of length 1, 2, 3, ...
• Tries $b$ branches at each step, where $b$ is max number of branches out of a state
• Example: if b is 3, try 1; 2; 3; 1,1; 1,2; 1,3; 2,1; 2,2; ... 3,3; 1,1,1; ...

Accepting/Recognizing a Language

• $L(M)$ is the language Accepted/Recognized by TM $M$
• $L(M)=\{w|M \textrm{ accepts } w\}$
• We say, $M$ accepts/recognizes $L$ iff
• $w \in L(M) \Rightarrow M$ halts on $w$ in accept state
• $w \notin L(M) \Rightarrow M$ halts on $w$ in reject state, or loops

Deciding a Language

• We say, $M$ decides $L$ iff
• $w \in L(M) \Rightarrow M$ halts on $w$ in accept state
• $w \notin L(M) \Rightarrow M$ halts on $w$ in reject state (ie does not loop)
• (ie $w \in L^C \Rightarrow M \textrm{ enters reject state}$

Turing Recognizable and Turing Decidable Languages

• Language $L$ is Turing Recognizable iff some TM $M$ recognizes $L$


• Language $L$ is Turing Decidable iff some TM $M$ decides $L$


• All languages we've seen so far have been TR and TD


• Later we will see: non-TR languages exist (more languages than TMs)

Example 1

• TM $M_1$: Transitions from start state:
• loop on 0 and move Right
• enter Accept on blank
• Enter reject state on 1


• What is $L_1 = L(M_1)$?


• Is $L_1$ TR?
• Is $L_1$ TD?

Example 2

• TM $M_2$: Transitions from start state:
• loop on 0 and move Right
• enter Accept on blank
• Enter Loop state on 1 (ie move left on all inputs, forever)
• In loop state, move Left on all inputs, forever)


• What is $L_2 = L(M_2)$?


• Does $M_2$ recognize $L_2$?
• Does $M_2$ decide $L_2$?


• Is $L_2$ TR?
• Is $L_2$ TD?


• Be careful of this distinction: Being TR/TD vs having a recognizer/decider
• If L has a Decider it is ...
• If L has a Recognizer it is ...

A Hierarchy of Languages

• All: ?? (All Languages is all sets of strings)
• TR: ??
• TD: $w\textrm{#}w$
• CF: $0^n1^n$
• RL: $0^n$

A Language that is TR but not TD

• Define a language that is TR but not TD in the context of integer roots to polynomials with integer coefficients


• Example polynomial: $7x^2y+3z$
• Set the polynomial equal to 0 to get a Diophantine equation
• Example Diophantine equation: $7x^2y+3z = 0$
• First look at polynomials in 1 variables
• Then look at polynomials in more than 1 variable

Polynomials in 1 Variable

• Some example polynomials in 1 variable:
1. $x^2+3x+2 $
2. $x^2+1 $
3. $7x^{23}+9x^{13}-3x^{10}+x^2-5 $


• Which have integer roots?

The Language of Polynomials with Integer Solutions

• Let $D_1$ be the language of all polynomials of one variable with integer roots
• Assume a proper encoding of polynomials as strings
• Are the polynomials above in this language


• TM $M_1$ determines whether polynomial $P$ is in $D_1$:
• Try all values for x: 0, 1, -1, 2, -2, 3, -3, ...
• If $x$ is a root for $P$, then accept
• If $x$ is a not root for $P$, then machine will loop


• Can we make $M_1$ halt?
• Yes: for any $P$, a limit for $x$ is known
• Only need to test up to that limit
• Modify $M_1$ so that it rejects if it reaches this limit


• IS $D_1$ TR? Is it TD?

Polynomials in Several Variables

• Consider 2 variables: $x$ and $y$
• Example: $7x^2y^3 + 9x^2y + 7x


• Let $D$ be the language of all polynomials of with any number of variables variables with integer roots


• Define machine $M$, similar to (modified) $M_1$ above: try $(x, y)$ values (0,0), (0,1), (1,0), (1,1), (0,2), ...
• Are there limits for x and y? Yes


• However, it has been proven that no limit exists for arbitrary number of variables


• Thus if $P \in D$, then $M$ halts and Accepts,
• But if $P \notin D$, then $M$ loops


• Is $D$ TR? Is it TD?

A TR but not TD Language

• You might ask, is there a clever TM that determines if there are integer roots without simply trying values
• It has been proven that there is not such a machine
• Can't do better than trying pairs
• This was done essentially by showing that Diophantine Equations and TMs are equivalent
• For every DE you can find an equivalent TM
• For every TM you can find an equivalent DE


• It has been proved (around 1970) that no TM can determine if an arbitrary polynomial has integer roots


• Thus, language D is Turing Recognizable but not Turing Decidable

Hilbert's Problems and What is Computation?

• In 1900 David Hilbert presented 23 most important math problems
• Hilbert: most famous, influential mathematician of his time


• Problem 10: Find a procedure for determining if a polynomial has integer roots
• As seen above, can be done for 1 or 2 variables, not for any number


• Problem 2: Find a general procedure for determining if a given statement can be proved from a set of axioms (and proof rules)

What is Computation

• Answer to problem 2 (and later problem 10) required a formal definition of computation


• Turing invented Turing Machines to show that Problem 2 cannot be solved
• Independently proved by Church (using functions - ie lambda calculus)
• Turing followed work by Godel

Godel's Theorem (1931)

• Any math system has true statements that cannot be proved to be true
• (Key Idea) Statement N: Statement N has no proof within the system
• If we could prove N, then N would have a proof and thus N would be false
• This is a contradiction
• Thus, we can't prove N, and so it is true


• Thus we have a statement that is true, but can't be proved (within the system)


• Formal proof is much more complicated

Church's Thesis

• Several definitions of computation have been invented
• Turing Machines
• Lambda Calculus (eg functions)
• Post Correspondence (like dominos - see text)
• Diophantine equations
• Others ...
• All have been proven to be equivalent
• Anything computable in one is computable in any


• Led to Church's Thesis:
• Anything that is computable, by any possible definition, is computable by a TM
• Is this provable?

Turing Complete Languages: The End to Language Wars

• Languages that can implement a TM are called Turing Complete
• Subject to time and memory limitation


• Turing Complete languages can calculate anything


• Thus, all Turing Complete languages are equivalent in power
• Although some are easier to use than others

Non TR Languages

• Next up: Non-TR languages


• Begin by defining language classes (eg A_DFA)