1. Describe a Turing machine that recognizes the language { a n + a²ⁿ + a³ ͫ n ϵ N} The symbol set is { a, +}, so this language contains things like a + aa + aaa and aa + aaaa + aaaaaa.
2. Describe a Turing machine that recognizes the language { aⁿ + a ͫ = aʳ: n + m = r, n, m, r ϵ N} The symbol set is { a, + , =}, so this language contains things like a + a = aa and aaa + aa = aaaaa.
Question
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
The Turing machine works in the following way,First is reads the ‘a’-s in the first segment. It reads a single ‘a’, marks that by ‘X’ and goes to state S2. Then it just ignores all ‘a’ until it gets the first ‘+’ sign. Then it marks the next two consecutive ‘a’ to the ‘+’ sign as ‘YY’ and again ignores everything until it gets the second ‘+’ sign....
Return to homework library