Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Quasi-regular grammars and languages.
Message-ID: <9663@uwm.edu>
Date: 21 Feb 91 03:08:26 GMT
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 53


   Here's an interesting concept.  Maybe someone has heard of something like it
before.

   A quasi-regular grammar consists of the following:

		    TERM: a set of terminals,
		    NON-TERM: a set of non-terminals,
		       with S in N: the start symbol,
		    PROD: a set of (regular) productions of the form
			    n -> E
                       with n an element of NON-TERM,
		       and E a regular expression over QUASI-TERM and TERM.
and in addition:
		    QUASI-TERM = {q1, q2, ..., qm}: a set of quasi-terminals,
                    BRACK = {a1, a2, ..., an, a1*, a2*, ..., an*}:
		       a set of conjugate bracket pairs
                    EMB: a set of embeddings of the form
		                qi -> a Ei a*
                       where
		       (1) Ei is a regular expression over TERM, QUASI-TERM,
			   and NON-TERM.
		       (2) a and a* are conjugate pairs out of BRACK.

All the sets T, N, P, and Q are distinct, each non-terminal has only one
production, each quasi-terminal has only one embedding, and two or more may
have embeddings involving the same bracket pair.

   As an example, a quasi-regular grammar describing additive expressions
might look like this:

		  TERM:       'a', '+'
		  NON-TERM:   Term = start symbol
		  PROD:       Term -> (('a' | B) ('+' ('a' | B))*
		  QUASI-TERM: B
		  BRACK:      '(', ')'
		  EMB:        B -> '(' Term ')'

This is regarded as equivalent to the context-free grammar specified in a
variant of EBNF:

		 Start-symbol: Term
		 Terminals: 'a', '+', '(', ')'
		 Non-Terminals: Term, B
		 Productions:
		    Term ->  (('a' | B) ('+' ('a' | B))*
		    B -> '(' Term ')'

The example should make it clear what it means for something to be considered
accepted by a quasi-regular grammar.

   Defining Quasi-Regular language as languages accepted by quasi-regular
grammars, the question naturally comes up: how powerful are these languages?


Brought to you by Super Global Mega Corp .com