About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
On context-free languages and push-down automata
Abstract
This note describes a special type of one-way, one-tape automata in the sense of Rabin and Scott that idealizes some of the elementary formal features used in the so-called "push-down store" programming techniques. It is verified that the sets of words accepted by these automata form a proper subset of the family of the unambiguous context-free languages of Chomsky's and that this property admits a weak converse. © 1963 Academic Press Inc.