• California State University, San Marcos

• CS 421

CS421 - Krell – HW4 (based on Weeks 13-15) (Use black for answers)

Turing Machines and Summary of Everything!

=================================================================

DUE: Week 15 Friday

TOTAL: 100 pts [15 % of total semester grade]

Provide your answer where there is a ?**?

?**? Name:

===================================================================

Be sure to read the context of each question first and give your answer

in the format requested.

===================================================================

===============================================

Week13b Review Question on TM [10 points]

===============================================

##Inter2* L = { a^n b^n | where n >= 1} using the transitions below, list all Trs() functions used for the

input ‘aab’ until you get stuck. [.5 point for each step - 4 points] ?**?

Trs(q0, a) = (q1, X, R) replace a with X and move right

Trs(q1, a) = (q1, a, R) skip over a's in search of b as moving right

Trs(q1, Y) = (q1, Y, R) skip over Y's in search of b as moving right

Trs(q1, b) = (q2, Y, L) found the b, replace it with Y, move Lef

Trs(q2, Y) = (q2, Y, L) skip over Y's to find a as moving lef

Trs(q2, a) = (q2, a, L) skip over a's to find X as moving lef

Trs(q2, X) = (q0, X, R) found X. The lef most a should be next to it.

Trs(q3, Y) = (q3, Y, R) moving right, skip over Y's to see if b remains

Trs(q3, blank) = (q4, blank, R) no more b's so accept the input in q4

········

In computing the subtraction function

Represent the input 8 - 3 on the tape: [2 points] ?**? ______________

What will the result of 8 - 3 look like on the tape ? [1.5 points] ?**? _____________

=============================================

Week14 - Week 15 Questions on Computability [.5 points each = 2.5 points]

=============================================

Q1. If you code the input in a ?**? __________________ language, a TM/program is guaranteed to halt.

Q2. The Universal TM takes ?**? a ______________ and ?**? _____________ as its input.

Q3: Can we write a program when the problem is Undecidable? ?**? ___________________

Why or why not? ?**? _______________________

Summary [90 points]

This section acts as the summary of everything you have learned.

In other words this is like your take-home final exam. You may not discuss with other people!!!!!

So, take your time to make it perfect.

I want a language that accepts 0 or more a’s follow by 2 b’s, followed by 1 or more c’s.

For example, my language will allow the following strings: abbc, aabbccc, bbc, aabbccccccc, etc.

What is the Regular Expression for this language using * and + [12 points]

?**? RE = __________________________

Draw the DFA diagram for this language, show the start and final states [15 points]

?**? *** DRAW DFA HERE ***

Write the function (hand-coded scanner like project part A for Word) for this DFA [15 points] ?**?

bool abcLanguage(string inputWord) // use states 0, 1, 2, etc..