Browse Prior Art Database

FPOL SYSTEMS GENERATING. LANGUAGES

IP.com Disclosure Number: IPCOM000128361D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

A. Ehrenfeucht: AUTHOR [+4]

Abstract

Counting languages are the languages of the form [Equation ommitted] are letters no two consecutive of which are identical. They possess a clean structure" in the sense that if an arbitrary word 'from such a language is cut in t subwords of equal length then no two.consecutive subwords contain an occurrence of the same letter. It is.shown that whenever an FPOL system G is.such that its. language contains a "dense enough" subset of a dounting language then the whole language of G cannot have such a. clean structure.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

FPOL SYSTEMS GENERATING. LANGUAGES

By A. Ehrenfeucht* and G. Rozenberg*

#CU-CS-113-77 September, 1977

A. Ehrenfeucht, Department of Computer Science,,University of Colorado-ai Boulder, Boulder, Colorado 8,0309 -USA

**G.:Rozen.berg, Department of Mathematics, University of Antwerp, U.I.A., Wilrijk, Belgium

ABSTRACT

Counting languages are the languages of the form

(Equation Omitted)

are letters no two consecutive of which are identical. They possess a clean structure" in the sense that if an arbitrary word 'from such a language is cut in t subwords of equal length then no two.consecutive subwords contain an occurrence of the same letter. It is.shown that whenever an FPOL system G is.such that its. language contains a "dense enough" subset of a dounting language then the whole language of G cannot have such a. clean structure.

I. INTRODUCTION

One of the important research areas in formal lan guage theory is the search for results describing the structure of a single language within a given language family. The classical example of such a result is the 11pumping lemma" for context free languages. It says that if certain words are.in a context free Ian guage then (.infinitely many) other words must be also,in this lan-guage.. Such results clearly shed some light on the generating abilities (restrictions) of grammars or machines) defining the given class of languages.

In this paper we establish a result in this direction for the class of languages generated by OL systems with-out.erasing productions and with.finite axiom sets (called FPOL systems).' One of the most popular type of languages. (serving as examples of strict inclusions of some classes of languages in others) in formal language theory are t-counting languages. These are languages of n n n the.form {4.a ... a t 2: 2,n 2: 11 where al,..,.,,a are t letters no two consecutive of which are identical. They possess a "clean structure" in the sense that.if an arbitrary word from.such a language is cut into t subwords of ,equal length then no two consecutive subwords share an occurrence of a common letter. We demonstrate that if an FPOL system G is such'tha.t. its language contains a. "dense enough" subset of a counting language, then the whole language cannot have such a clean structure (or even a. structure."approximating"it!). Thus again a result in this line: if certain words are.in the Ian-guage from the.given class then other words must also be in the.same language.

University of Colorado Page 1 Dec 31, 1977

Page 2 of 14

FPOL SYSTEMS GENERATING. LANGUAGES

Certainly there are very few results like th,is for the class of FPOL languages and we believe that this result together with its proof shed some newlight on the structure of derivations in FPOL systems.

Perhaps it is also worthwhile to mention that results like this are especially valuable in the theory of L forms where one is really interested in the structure...