Accession Number : AD0651226

Title :   PARTIAL ALGORITHM PROBLEMS FOR CONTEXT FREE LANGUAGES,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Ullian,Joseph S.

Report Date : 10 OCT 1966

Pagination or Media Count : 37

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.

Descriptors :   (*CONTEXT FREE GRAMMARS, ALGORITHMS), LANGUAGE, AUTOMATION, OPERATORS(MATHEMATICS), THEOREMS, MAPPING(TRANSFORMATIONS), SEQUENCES(MATHEMATICS), INEQUALITIES, MANAGEMENT ENGINEERING

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE