Browse Prior Art Database

DERIVATIVES AND QUOTIENTS OF PREFIX-FREE CONTEXT-FREE LANGUAGES

IP.com Disclosure Number: IPCOM000128696D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 24K

Publishing Venue

Software Patent Institute

Related People

CHARLES E. HUGHES: AUTHOR [+3]

Abstract

The complexity of a variety of decision problems for quotients and derivatives of prefix-free deterministic context-free-languages are investigated. The operations studied include the quotient of a language with itself and the successive application of the derivative operation. Each problem presented here is shown to be unsolvable and, moreover, each is shown to represent every r. e. many one degree of unsolvability.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DERIVATIVES AND QUOTIENTS OF PREFIX-FREE CONTEXT-FREE LANGUAGES

CHARLES E. HUGHES September 1978

ABSTRACT

The complexity of a variety of decision problems for quotients and derivatives of prefix-free deterministic context-free-languages are investigated. The operations studied include the quotient of a language with itself and the successive application of the derivative operation. Each problem presented here is shown to be unsolvable and, moreover, each is shown to represent every r. e. many one degree of unsolvability.

Index Terms: Context-free languages, decision problems, degrees of unsolvability, derivatives of languages, formal languages, prefix-free languages, quotient of languages, tag systems, unsolvable problems. i

1. INTRODUCTION

The object of this paper is to report on results attained concern-ing several decision problems related to sets produced by applications of the derivative and quotient operation:; to prefix-free context-free languages. In what follow we assume that our readers are familiar with the basic definitions of context-free languages and pushdown automata. Definition. A context-free language 1. is said to be deterministic if L is accepted by a deterministic pushdown automaton. L is called prefix-free if weL and wysL implies that y = a, the string of length zero. Prefix-free deterministic context-free languages have been studied by Harrison and Havel E2,31. In particular they have shown that this class of languages coincides with both a class they refer to as strict deterministic and the class of languages accepted by deterministic push-down automata with empty store. Mere we study operations on this class. The operations to be considered will now be defined.

Definition. Let L and S be arbitrary languages. Then the quotient of L with respect to S , denoted L/S, is the set

(Equation Omitted)

If S is a singleton set then the above operation is most often called the derivative of L with respect to S. The derivative and quotient operations have been studied by a number of authors. In particular, Hartmannis E43 has shown that every r. e. set may be represented as the quotient of two context-free languages. Closure properties of L/S, whenever S is a regular set are summarized in Hopcroft and Ullman E51. In particular deterministic context-free languages are closed under quotient with regular sets and consequently under the deriv-ative operation. However, prefix-free deterministic context-free languages are not, in general, closed under derivatives and hence not under quotient with regular sets. That this latter statement is true should be clear from the fact that, if no word in L contains a

University of Tennessee Page 1 Dec 31, 1978

Page 2 of 8

DERIVATIVES AND QUOTIENTS OF PREFIX-FREE CONTEXT-FREE LANGUAGES

(Equation Omitted)

is prefix-free but

(Equation Omitted)

is not necessarily so. Definition. Let L and S be arbitrary languages. Then the k-th...