Type 0 Grammar

Define a type 0 grammar that simulates a Turing Machine computation to accept the language (w w | w ∊ (0 + 1)*} The calculation can be done in three stages: For example, on input 10111011 Stage 1: Place an end marker at each end of the string: $10111011$ Stage 2: Move the end markers inward till they meet in the middle and mark the middle: 1011x1011 Stage 3: Go back and forth matching and crossing off symbols of the two strings. See the example grammar that accepts palindromes. To use the Python program: step 1: Click Rules and load a grammar rules file. Step 2: Click Run to initialize and run the simulation. When the program is paused, the step button can be used to run one step at a time. The simulation ends when no applicable re-writing rule is found. If at the end of the calculation the string contains non-terminals (capital letters), the input is rejected. If there are no uppercase letters the string is accepted. (Note, this is not exactly true. I took the quick approach and just checked islower() on the string. This returns true if there are no uppercase letters AND the string contains at least one lower case letter, so a string of all special characters will not be accepted). Notes about the program: The underscore _ is used to represent a blank. At startup, the input string has the start symbol placed at the beginning and the resulting string is padded with a blank at each end. The grammar rules file contains rules of the form: left-side → right-side The program actually just splits each line on white space and uses the first string as the left side and the last string on the line as the right side, so the arrow is not really needed. If a line contains just a single letter, that letter will be interpreted as the start symbol, otherwise the start symbol is S. You do not need to close and re-start the program to change rules. You can just select a new rules file and enter a new input string. Included are some example grammars: [login to view URL] Copies an input string, alphabet = {0, 1} [login to view URL] Accepts balanced (), alphabet = {(, )} [login to view URL] Mark string center, alphabet = {0, 1} [login to view URL] Accepts palindromes, alphabet = {0, 1} [login to view URL] Accepts anb nc n, alphabet = {a, b, c} The project grammar can first work like [login to view URL], then use a similar technique to [login to view URL] to check matching characters, but will scan both strings left to right, like [login to view URL] The program is a WIP and so is not as well organized as I would like, but it will do for the purpose of checking the project.