CS 475 Midterm: CS 475 Alabama Fall2017 Exam4 2
Document Summary
You may choose any set of problems that adds up to 100 or more points: write all the strings of lengths 2 and 4 that are accepted by this turing machine. X/x, l a/x, l c/x, l b/x, l d/x, l b/b, l d/d, l. B/b, r: write the 10 shortest positive lengths of the non-empty strings that can be generated by this unrestricted grammar. The terminal alphabet is just {a}, so it is sufficient to write just the lengths rather than the entire strings. [20 points for cs 475] [10 points for cs 575] Also write a precise simple definition of the language l that is generated by the above unrestricted grammar. For problems 3 and 4, let language l1 = { am bn | n is a multiple of m }. Examples: a2b10 = aabbbbbbbbbb, a3b9 = aaabbbbbbbbb, a4b8 = aaaabbbbbbbb: draw a deterministic turing machine that accepts language l1.
