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:
=============
...[Show More]
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..
[Show Less]