0
$\begingroup$

In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization of the grammar and the simplest type of parser required to implement it, and in a more formal description of same. The grammar is as follows:

<instruction> ::= <ident> "," <symbol> "," <operation> "," <ident> <EOL>
      <ident> ::= <char>
      <symbol ::= <char> | 'None'
  <operation> ::= <movement> | <write> <movement>
      <write> ::= 'P' <char> | 'E'
    <movement ::= 'R' | 'L'

An example Turing machine table written in this grammar is as follows:

b, None, P0R, c
c, None, R,   e
e, None, P1R, f
f, None, R,   b

It is clear to me that since this grammar is expressible in BNF, it must then be at most context-free, but is there a more accurate (more strict) categorization? The lack of left-recursion implies that it could be parsed with a recursive descent parser, but is there a simpler parser that would be capable of this grammar? How would one describe this grammar and its (simplest) associated parser?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

if you don't count rembering the symbols of previous lines it's a regular language here's the regex as I see it (<char> is translated to [a-z])

[a-z]\s*,\s*([a-z]|None)\s*,\s*(R|L|P[a-z](R|L))\s*,\s*[a-z]\n

use capturing groups as necessary ;)

Improve this answer
$\endgroup$
6
  • $\begingroup$ So then it's safe to say that the language is regular and the parser need only be a DSM? That's what I suspected, thanks. $\endgroup$
    – Rein Henrichs
    Sep 5, 2011 at 21:07
  • 1
    $\begingroup$ @Rein the control of a TM is usually represented as a finite-state machine which characterize regular languages, so you shouldn't be surprised that the grammar you described is regular. $\endgroup$
    – Artem Kaznatcheev ♦
    Sep 6, 2011 at 6:26
  • $\begingroup$ @Artem Good point, although in Turing's later examples he groups instructions by configuration name, which I believe would require a context-free grammar as ratchet freak implied? $\endgroup$
    – Rein Henrichs
    Sep 6, 2011 at 8:12
  • $\begingroup$ @rein what I meant with capturing groups is this I just named it for if you wanted to use the regex parser built into a lot of languages $\endgroup$
    – ratchet freak
    Sep 6, 2011 at 8:29
  • $\begingroup$ @ratchet I understand capturing groups. I was referring to your statement, "if you don't count rembering the symbols of previous lines it's a regular language". What if you do need to rememeber the symbols (idents) of previous lines, as Turing's later tables did? $\endgroup$
    – Rein Henrichs
    Sep 6, 2011 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.