CSC 341: March 9, 2007
From CSWiki
[edit]
Class notes
I wasn't able to prepare notes for today's lecture. Perhaps someone who took notes during class can supply his or hers?
[edit]
Study questions
- Give the sequence of configurations that the Turing machine M1 described in Figure 3.10 enters when started on the input 010#0100.
- Design a Turing machine on the alphabet
that always accepts its input, but only after moving it one position rightwards on the input tape (leaving a blank cell at the left end of the tape).
- Design a Turing machine that decides the non-context-free language
.
[edit]
Proposed Solutions
-
- The TM first traverses to the right end of its input (which will be the first blank space on the tape), then copies the character immediately to the left of the r/w head to the current cell. It then moves right one cell, and repeats the process. When the left end of the tape is reached, the TM accepts.
- The TM starts on the left edge of the tape, and if it finds anything other than an a or a blank there, it rejects. If it finds a blank, it accepts. If it finds an a, it replaces the a with an X, then scans through the input for a b. If it sees anything other than as before it finds the first b, it rejects. When it finds the first b, it replaces it with an X. Then It scans through the input for a c. If it sees anything other than bs before it finds the first c, it rejects. When it finds the first c, it replaces it with an X. Then it goes back to the leftmost cell of the tape, advances until it finds something other than an X, and if it is an a, it replaces with an X, otherwise it rejects. Then it advances until it finds something other than an a or an X, and if it is a b, it replaces it with an X. Then it advances until it finds something other than a b or an X, and if it finds something other than a c, it rejects. Otherwise it replaces the c with an X. And it keeps going in that manner until the first symbol it finds after the Xs is a blank, at which point it accepts, or something besides an a, at which point it rejects. If there are not enough bs or cs, the machine will have already rejected.
