Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!linac!att!ucbvax!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: <9102261256.AA16622@cyst.watson.ibm.com>
Date: 25 Feb 91 17:41:37 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Mark William Hopkins
Lines: 51
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?