PARTIAL ALGORITHM PROBLEMS FOR CONTEXT FREE LANGUAGES,
Abstract
By 'grammar' we mean context free grammar; when G is a grammar, L(G) is the language generated by G. Suppose a 'birdy' tells us of a given grammar G that there is a finite automaton accepting exactly the words in L(G). Can such an automaton be found. We understand this question (due to Ginsburg) as asking if there is an effective operator--a 'partial algorithm'--applicable to grammars and suitably defined for each grammar that generates a regular set. How the operator is to behave when applied to other grammars is not specified. We are able to answer questions of Ginsburg and Rose: On each of four construals, there is no partial algorithm for identifying, given grammars G1 and G2, a sequential machine, if one exists, mapping L(G1) to L(G2). Obtain the four construals by taking 'sequential machine' as either 'generalized sequential machine' or 'complete sequential machine' and 'mapping to' as either 'mapping onto' or 'mapping onto an infinite subset of'. Further partial algorithm problems are resolved, some of them concerning such families as bounded languages and sequences. We include several observations on the relationship between partial algorithm and associated decision problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 10, 1966
- Accession Number
- AD0651226
Entities
People
- Joseph S. Ullian
Organizations
- System Development Corporation