Simple deterministic languages
- 1 October 1966
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 36-46
- https://doi.org/10.1109/swat.1966.22
Abstract
The s-languages are those languages recognized by a particular restricted form of deterministic pushdown automaton, called an s-machine. They are uniquely characterized by that subset of the standard-form grammars in which each rule has the form Z → aY1...Yn, n≥0, and for which the pairs (Z, a) are distinct among the rules. It is shown that the s-languages have the prefix property, and that they include the regular sets with end-markers. Finally, their closure properties and decision problems are examined, and it is found that their equivalence problem is solvable. Since the solvability of the equivalence problem is not known for arbitrary deterministic languages, the s-languages are the most general class of languages for which this problem has been shown to be solvable.Keywords
This publication has 10 references indexed in Scilit:
- Deterministic context free languagesInformation and Control, 1966
- On the translation of languages from left to rightInformation and Control, 1965
- A New Normal-Form Theorem for Context-Free Phrase Structure GrammarsJournal of the ACM, 1965
- Decision Problems of Phrase-Structure GrammarsIEEE Transactions on Electronic Computers, 1964
- The Algebraic Theory of Context-Free LanguagesPublished by Elsevier ,1963
- Revised report on the algorithmic language ALGOL 60Communications of the ACM, 1963
- On the nonexistence of a phrase structure grammar for ALGOL 60Communications of the ACM, 1962
- On certain formal properties of grammarsInformation and Control, 1959
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946