**Converting Turing
Machine to an Unrestricted Grammar**

__Introduction____Converting
to an Unrestricted Grammar__

Export
and Parse

Any Turing machine can be converted to an unrestricted grammar.

JFLAP defines an unrestricted grammar as a grammar that is similar to a context-free grammar (CFG), except that the left side of a production may contain any nonempty string of terminals and variables, rather than just a single variable. In an unrestricted grammar, the left side of a production is matched, which may be multiple symbols, and replaced by the corresponding right hand side.

This conversion implements the
algorithm in the book “An Introduction to Formal Languages and
Automata 4^{th} Edition” by Peter Linz. The algorithm can
be founded on page 283-285.

There are 3 major steps that the algorithm follows in order to convert the Turing machine to an unrestrcted grammar. The first step is applying the basic rules from the start variable. It allows the grammar to generate an encoded version of any string q0w with an arbitrary number of leading and trailing blanks. The second step is applying generating the production for each transition of Turing machine. The last step is applying additional rules to our productions if we enter one of final states of TM, so we can derive terminals.

We will now convert the TM into an unrestricted grammar. First, open up the Turing Machine window and load the file verysimple_TM.jff.

Click on the **Convert → Convert to Unrestricted Grammar**
menu option, and the following screen should appear :

This is a very simple Turing
machine that accepts any language that has one or more “a”s. Just
like other conversion windows, you can click the **What's Left?**
button to view what states or transitions remain to be converted.

Now, let's produce our first
productions for our new grammar (the first step of algorithm). By
default, there are going to be 3 productions that are going to be
produced for every TM that is going to be converted. These three
rules are

“S->V(==)S, S->SV(==), S->T”, where S is
the start variable. In addition there are going to be 2 additional
rules “T->TV(aa), T->V(a0a)”, in which “a” refers to
for all readable strings in the tape. The result of productions
generated by the first step can be viewed by clicking initial state
q0. Note that “=” refers to the blank tape symbol in the Turing
machine. After clicking the state q0, your window would look like
this :

Now, let's move on to the second step of algorithm and examine our first transition from q0 to q1. The transition is (q0, a) => (q1, a, R). By following the algorithm, we are going to place production V(x0a)V(yz) → V(xa)V(y1z), where x, y is all elements of input alphabet+blank symbol and z is all elements of the tape alphabet. Since we only have “a” in our input alphabet our x and y is going to be “a”. “z” can be either “a” or “=” (blank). Also, since q1 is final state, we have to apply the last step of algorithm . We apply the special rule V(a1a) → a and yV(xz) → a, where x and y are all the input alphabet + blank symbol (=) and z is all of our tape alphabets. By doing so, we can generate terminals on the right hand side of productions. After applying all of these rules, our grammar window would look like :

After either clicking our
last transition in q1 or using **Show All** button, we can finish
our conversion.

Let's now export this
converted grammar. You can click on **Export** button to export
this grammar. After exporting the grammar, your window would look
like this :

Now let's try to parse this
unrestricted grammar, note that V(aa) is actually refers to one
variable. Click on **Input **and **Parser for Converted Grammar
from TM**. You will see very similar grammar parse pane from brute
force parsing. In this parser, all the variables such as V(aa) is
trimmed into regular variable like “A” or “B”, so the parsing
can occur. This trimming procedure is done internally in the parser.
In the input, type in string “aa”. You can see that the this
string is accepted by the language as expected. Click on **STEP**
buttons several times to see how we derive this string. You can
either view the derivation in Noninverted tree or Derivation table.
Your result should look like one of these windows.

**NOTE**: The JFLAP
Parser recognizes this special notation in the grammar. It converts
varaibles such as V(aa) into normal variables like “A” in the
background to facilitate the parsing.

**WARNING:** This only
works with very small examples since the conversion is exponential.

Now let's try to input “aaaaaaaa” (8 a's). The parser quickly accepts the language, but note that there are 271 nodes generated for such a simple string. This reveals that the parser is going to have really hard time parsing other complicated grammar such as a^nb^nc^n. As Turing machine gets more complicated, the parsing of converted grammar would get more difficult and almost impossible. Although the converted grammar might not be useful in actually checking the string, it proves that TM can be converted to unrestricted grammar.

**NOTE:** You can also
use user control parser to derive the string manually.

Another example of converting TM to unrestricted grammar is shown in below windows. You can load the file anothersimple_TM.jff to load this example. Note that it generated 21578 nodes to just to accept simple string “ab”.

**This concludes our brief
tutorial on converting Turing machine into an unrestricted grammar.
Thanks for reading!**