Access Restriction

Author Ginsburg, Seymour ♦ Ullian, Joseph
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1966
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Various elementary operations are studied to find whether they preserve on ambiguity and inherent ambiguity of language (“language” means “context-free language”) The following results are established:If $\textit{L}$ is an unambiguous language and $\textit{S}$ is a generalized sequential machine, then (a) $\textit{S}(\textit{L})$ is an unambiguous language if $\textit{S}$ is one-to-one on $\textit{L},$ and (b) $\textit{S}-1(\textit{L})$ is an unambiguous language.Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words.The product (either left or right) of a language and a word preserves both unambiguity and inherent ambiguity.Neither unambiguity nor inherent ambiguity is preserved by any of the following language preserving operations: (a) one state complete sequential machine; (b) product by a two-element set; (c) $\textit{Init}(\textit{L})$ = $[\textit{u}$ ≠ dur in $\textit{L}$ for some $\textit{v}];$ (d) $\textit{Subw}(\textit{L})$ = $[\textit{w}$ ≠ durr in $\textit{L}$ for some $\textit{u},$ $\textit{v}].$
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 1966-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 13
Issue Number 3
Page Count 5
Starting Page 364
Ending Page 368

Open content in new tab

   Open content in new tab
Source: ACM Digital Library