Question: you are asked to write three programs (for Questions 1.2.9, 1.2.10 and 1.2.11) that compute the answers. Note: your outputs should match the results that
you are asked to write three programs (for Questions 1.2.9, 1.2.10 and 1.2.11) that compute the answers.
Note: your outputs should match the results that are given in the answers provided; as long as the contents are the same, there is no need to list the results in the same order.
You have to include a README file that explains if you are getting the same answers as provided. If your program does not run correctly, be sure you state it in README.
We hope that the students using this project will not find Shepherdsons construction tricky, but instead will find that it makes a lot of sense and is the logical way to go for proving the equivalence result. Students will be required to read from the verbal explanations given by Shepherdson, and derive from it computer programs for solving problems in this project.
1.2 Project
The following 10-state 2DFA A1, where q0 is the starting state and q9 is the only final state, systematically checks every possible 6-symbol subsequence to see if it begins and ends with 1s.
| current state | symbol | new state | go to |
| q0 | 0 | q0 | R |
| q0 | 1 | q1 | R |
| q1 | 0 or 1 | q2 | R |
| q2 | 0 or 1 | q3 | R |
| q3 | 0 or 1 | q4 | R |
| q4 | 0 or 1 | q5 | R |
| q5 | 0 | q6 | L |
| q5 | 1 | q9 | R |
| q6 | 0 or 1 | q7 | L |
| q7 | 0 or 1 | q8 | L |
| q8 | 0 or 1 | q0 | L |
| q9 | 0 or 1 | q9 | R |
1.2.1 Demonstrate the steps performed by A1 in accepting the tape 11001010.
1.2.2 Demonstrate the steps performed by A1 in processing the tape 11001001. Conclude that the tape is not accepted by A1.
Another example 2DFA A2 (taken from Example 2.14 of the textbook by Hopcroft and Ullman [1]) is given as follows, where q0 is the starting state and F = {q0,q1,q2}:
| current state | symbol | new state | go to |
| q0 | 0 | q0 | R |
| q0 | 1 | q1 | R |
| q1 | 0 | q1 | R |
| q1 | 1 | q2 | L |
| q2 | 0 | q0 | R |
| q2 | 1 | q2 | L |
1.2.3 Demonstrate that the input 101001 is accepted by A2.
1.2.4 Demonstrate that the input 10111 is not accepted by A2. Indeed, A2 will run into an infinite loop.
Given the description of a 2DFA, Shepherdson explained how to derive the description of an equivalent DFA that accepts the same set of inputs. The following is an excerpt (modified slightly) from Shepherdson [6] describing the construction:
The only way an initial portion t of the input tape can influence the future behaviour of the two-way machine A when A is not actually scanning this portion of the tape is via the state transitions of A which it causes. The external effect of t is thus completely determined by the transition function, or table, t which gives (in addition to the state in which the machine originally exits from t), for each state q of A in which A might re-enter t, the corresponding state q0 which A would be in when it left t again. This is all the information the machine can ever get about t however many times it comes back to refer to t; so it is all the machine needs to remember about t. But there are only a finite number of different such transition tables (since the number of states of A is finite), so the machine has no need to use the input tape to supplement its own internal memory; a one-way machine A with a sufficiently large number of internal states could store the whole transition table t of t as it moved forward, and would then have no need to reverse and refer back to t later. If we think of the different states which A could be in when it re-entered t as the different questions A could ask about t, and the corresponding states A would be in when it subsequently left A again, as the answers, then we can state the result more crudely and succinctly thus: A machine can spare itself the necessity of coming back to refer to a piece of tape t again, if, before it leaves t, it thinks of all the possible questions it might later come back and ask about t, answers these questions now and carries the table of question-answer combinations forward along the tape with it, altering the answers where necessary as it goes along.
To summarize Shepherdsons idea, we need to maintain for each prefix t two pieces of information: (1) the state in which the machine exits from t (when starting at q0 in the leftmost square of the input), and (2) the external effect t.
Let us refer to the processing of the input tape 101001 by A2. Consider the first symbol of the input which is a 1. That is, let t = 1.
To answer the first question, we observe that when A2 begins with the initial state q0 at the symbol 1, it will exit t to its right at state q1.
Next, we summarize the external effect t where t = 1 by answering the following questions:
Suppose later in the processing of the input, the first symbol 1 is revisited by a left movefrom the right. What will be the effect if it is revisited with a state q0?
Suppose later in the processing of the input, the first symbol 1 is revisited by a left movefrom the right. What will be the effect if it is visited with a state q1?
Suppose later in the processing of the input, the first symbol 1 is revisited by a left movefrom the right. What will be the effect if it is visited with a state q2?
Verify that the answers to the 3 questions are: (1) move right at state q1, (2) move left at state q2 and (3) move left at state q2. In short the external effect can be succinctly summarized as a 3-tuple [(q1, R), (q2, L), (q2, L)].
We combine the two pieces of information computed in a 4-tuple [(q1, R), (q1, R), (q2, L), (q2, L)]. Let us call this 4-tuple the effect of t where t = 1. Note that the first entry is the answer to the first question, whereas the next 3 entries are the external effect of t. That is, the effect of t is the total effect, which is more than just the external effect.
Next, given the effect computed for the first symbol 1, we want to compute the effect of the first two symbols 10 of the input 101001.
From the effect [(q1, R), (q1, R), (q2, L), (q2, L)] of the symbol 1, we know that the machine exits 1 to its right with the state q1. Thus, the machine is at state q1 when visiting the second symbol 0. According to the transition table, the machine will again move to the right of the second symbol at state q1.
To compute the external effect of t = 10, we have to answer the following questions:
Suppose later in the processing of the input, the second symbol 0 is revisited by a left movefrom the right. What will be the effect if it is revisited with a state q0?
Suppose later in the processing of the input, the second symbol 0 is revisited by a left movefrom the right. What will be the effect if it is visited with a state q1?
Suppose later in the processing of the input, the second symbol 0 is revisited by a left movefrom the right. What will be the effect if it is visited with a state q2?
The answers are as follows:
When the second symbol 0 is revisited with a state q0, the machine according to the transition table will move to the right with the state q0.
When the second symbol 0 is revisited with a state q1, the machine according to the transition table will move to the right with the state q1.
When the second symbol 0 is revisited with a state q2, the machine according to the transition table will move to the right with the state q0.
Therefore, the effect of t = 10 is summarized in the 4-tuple [(q1, R), (q0, R), (q1, R), (q0, R)].
Note that in the above computations, we do not make use of the external effect computed for the first prefix 1 to compute the effect for the prefix 10. This is not usually the case. In general, the external effect for t is needed in computing the new effect when t is extended by one more symbol.
1.2.5 Next, with the answers [(q1, R), (q0, R), (q1, R), (q0, R)] for the effect for 10, compute the effect when the input is extended by the third symbol 1.
From the effect for 10, we know that the machine arrives at the third symbol 1 at state q1. According to the transition table, the machine will move to the left to the 2nd symbol at state q2. Next, consulting the last entry of the effect for 10, we know the machine will leave 10 to its right at state q0. Thus, the machine revisits the third symbol 1 at state q0. Again, from the transition table, the machine moves to the right at state q1. Verify that the external effect of 101 is [(q1, R), (q1, R), (q1, R)]. That is, the effect for 101 is [(q1, R), (q1, R), (q1, R), (q1, R)].
In answering question 1.2.5, you should provide the steps involved in computing the external effect for 101.
Note that given the effect for t and a new symbol 1, we can compute the effect for t0 = t1 by referring to the transition table for the machine. There is no need to know what t is. Only the effect for t is needed in computing the new effect for t0.
1.2.6 Repeatedly, compute the effects by extending the current input 101 with symbols 0, 0, 1. From the effect computed for 101001, conclude that the input is accepted. Recall that 101001 was shown in 1.2.3 to be accepted by A2.
1.2.7 Repeat the whole exercise with the input 10111 as in 1.2.4. Conclude that the input 10111 is not accepted.
To summarize, in simulating A2 by a DFA, we need only remember the effect of the sequence of input symbols that has been processed so far.
1.2.8 How many different effects can there be in simulating A2 by a DFA? How many states are needed for a DFA to accept the same set of inputs as A2? Note that there are only finitely many different effects even though we have an infinite number of inputs of finite lengths.
1.2.9 Applying Shepherdsons method to A1, how many states are there in the DFA constructed?
The work involved is very tedious. It is impossible to do it by hand. You should write a program to perform the computation.
Note that the smallest DFA[8] accepting the same set of inputs as A1 has 33 states.
In computer programming, we can detect if the end-of-input has been reached. For example, in C programming, we write while ((input=getChar()) != EOF)
Thus, it is very reasonable to extend the 2DFA model so that the machine can detect the two ends of an input tape.
Read the following excerpt (modified slightly) from Shepherdsons paper [6] regarding extending the 2DFA model by providing each input tape with special marker symbols b, e at the beginning and end of the input. Let us call this new model 2DFA-with-endmarkers.
At first sight it would appear that with a two-way automaton more general sets of tapes could be defined if all tapes were provided with special marker symbols b, e (not in ) at the beginning and end, respectively. For then it would be possible, e.g., to design a twoway machine which, under certain conditions, would go back to the beginning of a tape, checking for a certain property, and then return again. This would appear to be impossible for an unmarked tape because of the danger of inadvertently going off the left-hand edge of the tape in the middle of the computation. In fact, the machine has no way of telling when it has returned to the first symbol of the tape. However, the previous construction result implies that this is not so; that the addition of markers does not make any further classes of tapes definable by two-way automata. For if the set {b}U{e} (of all tapes of the form bte for t U) is definable by a two-way automaton then it is definable by a one-way automaton; and it is easy to prove that {b}U{e} is definable by a one-way automaton if and only if U is.
We assume that a 2DFA-with-endmarkers starts on the left endmarker b at the initial state.
Suppose we want to design a 2DFA-with-endmarkers over = {0,1} to accept input tapes that has a symbol 1 in the sixth position from the right end. For example, the input 10101011 has 8 symbols with the third symbol being a 1, which is the sixth position from the last (eighth) position. The following 2DFA-with-endmarkers A3, where q0 is the starting state and q9 is the accepting state, accepts the input tapes described. Observe that an accepted input must begin with b and end with e. Furthermore, b and e do not appear in other positions of the string accepted.
| current state | symbol | new state | go to |
| q0 | b | q1 | R |
| q1 | 0 or 1 | q1 | R |
| q1 | e | q2 | L |
| q2 | 0 or 1 | q3 | L |
| q3 | 0 or 1 | q4 | L |
| q4 | 0 or 1 | q5 | L |
| q5 | 0 or 1 | q6 | L |
| q6 | 0 or 1 | q7 | L |
| q7 | 1 | q8 | R |
| q8 | 0 or 1 | q8 | R |
| q8 | e | q9 | R |
1.2.10 Following the discussion by Shepherdson and based on the definition of A3, explain the construction of a DFA equivalent to A3 accepting the same set of input tapes where the inputs are delimited by b and e. How many states does the DFA have? Next, modify the DFA constructed to accept inputs with the endmarkers b and e removed. What is the change in the number of states of the DFA?
As in 1.2.9, you should write a program to perform the computation.
Note that it can be shown that the smallest DFA accepting the same set of inputs (without the endmarkers b and e) as A3 has 64 states.
Consider another 2DFA-with-endmarkers A4, where q0 is the starting state and q9 is the accepting state, as defined below.
| current state | symbol | new state | go to |
|
| q0 | b | q1 | R |
|
| q1 | 0 or 1 | q1 | R |
|
| q1 | e | q2 | L |
|
| qi | 0 | qi+1 | L | i = 2,3,4 |
| qi | 1 | qi | L | i = 2,3,4 |
| q5 | 0 | q7 | L |
|
| q5 | 1 | q6 | L |
|
| q6 | 0 | q6 | L |
|
| q6 | 1 | q7 | L |
|
| q7 | 0 | q7 | L |
|
| q7 | 1 | q5 | L |
|
| q7 | b | q8 | R |
|
| q8 | 0 or 1 | q8 | R |
|
| q8 | e | q9 | R |
|
1.2.11 Re-do part 1.2.10 for A4.
Note that it can be shown that the smallest DFA accepting the same set of inputs (without the endmarkers b and e) as A4 has 64 states.
Below are the answers for the 2-way DFA project.
1.2.9
The number of effects (including the initial effect) = 79.
States are accepting when the first entry of the effect is (q9,R).
Below is a list of the 79 states/effects:
[initial effect]
[(q0,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q6,L),(q7,L),(q8,L),(q0,L),(q9,R)]
[(q1,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q7,L),(q8,L),(q0,L),(q9,R)]
[(q0,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q7,L),(q8,L),(q0,L),(q0,R),(q9,R)]
[(q1,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q8,L),(q0,L),(q1,R),(q9,R)]
[(q2,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q7,L),(q8,L),(q0,L),(q2,R),(q9,R)]
[(q2,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q8,L),(q0,L),(q2,R),(q9,R)]
[(q0,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q8,L),(q0,L),(q0,R),(q0,R),(q9,R)]
[(q1,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q0,L),(q1,R),(q1,R),(q9,R)]
[(q2,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q8,L),(q0,L),(q2,R),(q2,R),(q9,R)]
[(q2,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q0,L),(q2,R),(q2,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q8,L),(q0,L),(q3,R),(q0,R),(q9,R)]
[(q3,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q0,L),(q3,R),(q1,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q8,L),(q0,L),(q3,R),(q2,R),(q9,R)]
[(q3,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q0,L),(q3,R),(q2,R),(q9,R)]
[(q0,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q0,R),(q0,R),(q0,R),(q9,R)]
[(q1,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q1,R),(q1,R),(q1,R),(q9,R)]
[(q2,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q2,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q3,R),(q3,R),(q0,R),(q9,R)]
[(q3,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q1,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q3,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q4,R),(q0,R),(q0,R),(q9,R)]
[(q4,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q1,R),(q1,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q4,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q4,R),(q3,R),(q0,R),(q9,R)]
[(q4,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q1,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,L),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q4,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q0,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,R),(q0,R),(q0,R),(q0,R),(q9,R)]
[(q2,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q2,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q3,R),(q3,R),(q3,R),(q0,R),(q9,R)]
[(q3,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q3,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q0,R),(q0,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q3,R),(q0,R),(q9,R)]
[(q4,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q0,R),(q0,R),(q0,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q1,R),(q1,R),(q1,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q3,R),(q3,R),(q0,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q1,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q0,R),(q0,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q1,R),(q1,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q3,R),(q0,R),(q9,R)] [(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q1,R),(q9,R)]
[(q5,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q5,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q1,R),(q1,R),(q1,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q1,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q1,R),(q1,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q1,R),(q9,R)]
[(q9,R),(q1,R),(q2,R),(q3,R),(q4,R),(q5,R),(q9,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q2,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q3,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q2,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q3,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q2,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q3,R),(q2,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q3,R),(q3,R),(q3,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q3,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q3,R),(q3,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q3,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q4,R),(q4,R),(q0,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q4,R),(q0,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q5,R),(q0,R),(q0,R),(q0,R),(q9,R)]
[(q9,R),(q0,R),(q2,R),(q3,R),(q4,R),(q5,R),(q0,R),(q0,R),(q0,R),(q0,R),(q9,R)]
1.2.10
Below is a DFA for the language of A_3 for inputs including endmarkers.
The number of effects (including the initial effect) = 68.
States are accepting when the first entry of the effect is (q9,R).
Below is a list of the 68 states/effects:
[initial effect]
[ dead ]
[(q1,R),(q1,R), loop , loop , loop , loop , loop , loop , loop , loop , loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop , loop , loop ,(q8,R), loop ] [(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q9,R), loop ,(q9,R), loop , loop , loop , loop , loop , loop ,(q9,R), loop ]
To obtain a DFA for the same language without the endmarkers,
we do not need the two states corresponding to the initial effect and the effect with the first entry (q9,R), which are the first and last effect in the above list of effects. Also, the second effect correspond to a dead state, which again is not needed. The resulting DFA has 65 states with the third effect as the starting state.
1.2.11
Below is a DFA for the language of A_4 for inputs including endmarkers.
The number of effects (including the initial effect) = 68.
States are accepting when the first entry of the effect is (q9,R).
Below is a list of the 68 states/effects:
[initial effect]
[ dead ]
[(q1,R),(q1,R), loop , loop , loop , loop , loop , loop ,(q8,R), loop , loop
]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop , loop ,(q8,R),(q8,R), loop
]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q9,R), loop ,(q9,R), loop , loop , loop , loop , loop , loop ,(q9,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop ,(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop , loop , loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop , loop , loop ,(q8,R), loop ] [(q1,R), loop ,(q1,R), loop ,(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop , loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop , loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop , loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R),(q8,R),(q8,R),(q8,R), loop ]
[(q1,R), loop ,(q1,R), loop ,(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R),(q8,R), loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop , loop ,(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R),(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop ,(q8,R), loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R),(q8,R), loop , loop ,(q8,R), loop ]
[(q1,R), loop ,(q1,R),(q8,R), loop ,(q8,R), loop , loop ,(q8,R),(q8,R), loop ]
To obtain a DFA for the same language without the endmarkers,
we do not need the two states corresponding to the initial effect and the effect with the first entry (q9,R). Next, it is observed that the [ dead ] effect is not needed.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help