Thumbnail
Access Restriction
Subscribed

Author Lomet, David Bruce
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1973
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The transition diagram systems first introduced by Conway are formalized in terms of a restricted deterministic pushdown acceptor (DPDA) called a nested DPDA. It is then established that the class of nested DPDA's is capable of accepting all deterministic context-free languages. The proof of this involves demonstrating that left recursion can be eliminated from deterministic (or $LR(\textit{k}))$ grammars without destroying the deterministic property. Using various structural properties of nested DPDA's, one can then establish equivalence results for certain classes of deterministic languages.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1973-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 2
Page Count 23
Starting Page 235
Ending Page 257


Open content in new tab

   Open content in new tab
Source: ACM Digital Library