Question

Hi, this is an automata question, please both Write and Draw a graph for this turing machine, with detailed explanation. Thank you in advance!

Let a directed graph be a tuple (V, E) where V & N a set of edges (with natural numbers as names), and E is a relation in V. For example, ?(1,2},{(1,1),(1,2),(2,1),(22)? is a directed graph, as is ?{},{}?, as is <(1,33},{(1,1),(33, 33». Write a TM that accepts on any valid directed graph description, over the alphabet l'I,,'',',',?,0,1, 2, 3, 4, 5, 6, 7, 8,9), and rejects otherwise. For this problem, you do not need to check that the edges match the set ofvertices.

Answer 1

The turing machine will do the following. It will check that the input starts with "<" or not. Otherwise, simply reject. Then, it will check whether there is a "{" or not. Otherwise, simply reject. Then either "}" follows or must follow numbers, separated by comma, before encountering an "}". If it encounters anything else, simply reject. If just before "}" there is a comma, again reject. Then, there must be a comma after "}". Then immediately a "{" must follow. Then either a "}" or a "<" must follow. If "<" is seen, then numbers should come in pair, and finish with ">". At the end there must be a "}" and ">". The input must finish here. Any other case, and the machine will reject. Note that you don't need to remember which nodes occured, as you don't need to match edges with vertices.

The machine is as follows. States $\{q_0, q_1, q_2, q_2^\prime, q_3, q_4, q_5, q_6, q_7, q_8, q_9, q_{10}, q_{11}, q_{12}, q_{13}, q_{14},q_{f}\}$ , initial state $q_0$ , alphabet and tape alphabet both $\Sigma = \Gamma = \{'\{', '\}', ',', \langle, \rangle, 0,1,2,3,4,5,6,7,8,9\}$ . For simplicity, denote all digits with in the transition table. is the blank alphabet. The final state is only $q_f$ . Following is the table for the transition function. The machine only scans the input, never changes it, thus no need to specify what the machine writes when the head moves. Also, the head always moves right, so no need to specify that either. There are no transitions out of the final state.

	{	}	,	$\langle$	$\rangle$	d	#
$q_0$				$q_1$
$q_1$	$q_2$
$q_2$		$q_4$				$q_2^\prime$
$q_2^\prime$			$q_3$			$q_2^\prime$
$q_3$						$q_2$
$q_4$			$q_5$
$q_5$	$q_6$
$q_6$		$q_{14}$		$q_7$
$q_7$						$q_8$
$q_8$			$q_9$			$q_8$
$q_9$						$q_{10}$
$q_{10}$					$q_{11}$	$q_{10}$
$q_{11}$		$q_{13}$	$q_{12}$
$q_{12}$				$q_{7}$
$q_{13}$					$q_{14}$
$q_{14}$							$q_{f}$

The diagram looks like this,

start o 41 42 93 If 914 46 413 97 412 q10 - (9 48