[comp.theory] Quasi-regular grammars and languages.

markh@csd4.csd.uwm.edu (Mark William Hopkins) (02/21/91)

   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?

markh@CSD4.CSD.UWM.EDU (Mark William Hopkins) (02/26/91)

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?