<!-- 
     DTD for the Turing Machine Markup Language (TMML), version 0.1. 

     A TMML document specifies a Turing machine. For more information
     about Turing machines and TMML, please refer to the XSLT stylesheet
     that is available at https://www.thelyonsfamily.us/turing/utm.xsl. This
     stylesheet is a Universal Turing Machine that executes the
     Turing machines that are defined by TMML documents.

     This DTD is available at https://www.thelyonsfamily.us/turing/tmml.dtd.

     Developed by Bob Lyons.
-->

<!-- 
     Copyright (c) 2001. Robert C. Lyons. All rights reserved.
-->

<!-- A Turing machine consists of symbols, states and a transition function.
-->
<!ELEMENT turing-machine      ( symbols, states, transition-function ) >

<!-- The turing-machine element must contain the version attribute,
     which must be equal to "0.1".
-->
<!ATTLIST turing-machine
          version             CDATA                  #IMPLIED >

<!-- The symbols element defines the symbols supported by the
     Turing machine. Each character in the content of the 
     symbols element is a member of the set of symbols. Thus,
     each symbol is a Unicode character. At least one symbol
     must be defined by the symbols element (in other words,
     the length of the content of the symbols element must be
     at least one). The blank-symbol attribute 
     of the symbols element defines the blank symbol for the
     Turing machine. By default, the blank symbol is the space
     character. None of the symbols that are defined by the
     content of the symbols elements may be the blank symbol.
     Each symbol on the input tape must be equal to the blank
     symbol or one one the symbols defined in the content of the
     symbols element. 
-->
<!ELEMENT symbols             (#PCDATA) >

<!ATTLIST symbols
          blank-symbol        CDATA                  ' ' >

<!-- The states element contains one or more state elements. 
-->
<!ELEMENT states              ( state+ ) >

<!-- Each state element defines a state in the Turing machine. 
     The value of each state element must not be null and it
     must not contain any whitespace characters. Also, the states
     must be unique. In other words, if one of the state elements
     contains "state1", then none of the other state elements may
     contain this value.

     There must be exactly one start state. The initial state of
     the Turing machine is the start state. The start state is the
     state element that includes the start attribute that is set to
     'yes'.

     There must be one or more halt states. The Turing machine halts
     when it enters one of the halt states. A halt state is a
     state element that includes the halt attribute that is set to
     'yes'.
-->
<!ELEMENT state               ( #PCDATA ) >

<!ATTLIST state
          start               (yes|no)               'no'
          halt                (yes|no)               'no' >

<!-- The transition function maps the current state and the
     current symbol to the next state, the next symbol and the
     movement for the tape head. The transition function contains one or
     more mappings. Each mapping maps from a ( state, symbol )
     pair to a ( state, symbol, movement ) triplet.
-->

<!ELEMENT transition-function ( mapping+ ) >

<!-- A mapping consists of the from-side of the mapping and the
     to-side of the mapping. The from-side of each mapping must
     be unique. For example, if there is a mapping element in which the
     the current state is "x" and the current symbol is "1", then
     must not be another mapping element in which the current state is
     "x" and the current symbol is "1".
-->

<!ELEMENT mapping             ( from, to ) >

<!-- The from element contains the current-state and current-symbol
     attributes. The current state is the state that the Turing machine
     is in when it invokes the transition function. The current symbol 
     is the symbol on the tape under the Turing machine's tape head
     when the Turing machine invokes the transition function.

     The value of the current-state attribute must be one of the
     states defined in the states element.

     The value of the current-symbol attribute must be one of the
     symbols defined in the symbols element or must be equal to the
     blank symbol.
-->

<!ELEMENT from                EMPTY >

<!ATTLIST from
          current-state       CDATA                  #IMPLIED
          current-symbol      CDATA                  #IMPLIED >

<!-- The to element contains the next-state, next-symbol and movement
     attributes. Each time the Turing machine invokes the transition
     function, it changes its state from the current state to the
     next state. It then overwrites the current symbol on the tape
     with the next symbol. The Turing machine then moves its tape
     head one symbol to the left, one symbol to the right or not at
     all, depending on the value of the movement attribute.

     The value of the next-state attribute must be one of the
     states defined in the states element.

     The value of the next-symbol attribute must be one of the
     symbols defined in the symbols element or must be equal to the
     blank symbol.

     The value of the movement attribute must be 'left', 'right'
     or 'none'.
-->
<!ELEMENT to                  EMPTY >

<!ATTLIST to
          next-state          CDATA                  #IMPLIED
          next-symbol         CDATA                  #IMPLIED
          movement            (left|right|none)      #IMPLIED >