Programming Language for Automata

ABSTRACT

The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other classes of automata. The second part of this paper shows how this programming language can be applied to automata theory, as we prove there are non-context-sensitive languages accepted by a stack automaton.

REFERENCES

• 1: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
• 2: M. W. Curtis, A Turing Machine Simulator, Journal of the ACM (JACM), v.12 n.1, p.1-13, Jan. 1965 [doi>10.1145/321250.321251]
• 3: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 4: KURODA, S. Y. Classes of lauguages and linear bounded automata. Inf. Coat. 7 (1964), 202-223.
• 5: CAINE, STEPHEN H. Reference manual for CIT 7090/7094 experimental macro assembly program (XMAP). California Institute of "Ichnology, Pasadena, Calif. April 2,4, 1964.
• 6: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Design, Languages, Performance, Theory, Verification