- Use the macro TM language to write a decider for the language
L={x - y = z : x,y,z ∈ 1+}.
To clarify: the input alphabet for this language is Σ={-,=,1}
and "11-111=1"∈ L. Quotation marks added for clarity; they're not part of the string. Blanks aren't part of
the string, either.
- Hint: This is very similar to the first problem in HW 8a.
- This machine will be used in problem 8, in the next set.
- Consider the encoded DTM <M1> below in which
$\Sigma=\{a,b\}$ and $\Gamma=\{\square, a, b, \$\}$.
Using Examples 17.19 and 17.20 as a pattern, do the following:
- Complete the table below which shows the encoding of the tape symbols.
Symbol | Encoding |
$\square$ | |
a | |
b | |
$ | |
- Draw the machine that the encoding below represents.
- Precisely and concisely describe the language accepted by M1.
- Hint: In the next question you can discover one of the strings that's in the language.
Machine Encoding:
<M1> = (q000, a00, Y011, a00, R),
(q000, a01, q001, a11, R),
(q000, a10, N100, a10, R),
(q000, a11, q000, a11, R),
(q001, a00, N100, a00, R),
(q001, a01, q001, a01, R),
(q001, a10, q010, a11, L),
(q001, a11, q001, a11, R),
(q010, a00, q000, a00, R),
(q010, a01, q010, a01, L),
(q010, a10, N100, a10, R),
(q010, a11, q010, a11, L)
-
Consider the language L = {<M, w> : M accepts w}.
One string in this language is <M1,ab> = <M1>,a01a10, where <M1> is the encoding
of machine M1, as given above.
- Give another two strings in this language, following the pattern above
(ie < M1, w> = <M1>,z, where z ∈ {a,b}*).
- Show a string <M1,w> that is NOT in the language, following the pattern
(ie < M1, w> = <M1>,z, where z ∈ {a,b}*).
- Hint: This problem is very easy once you know the language; you just have to apply definitions.