1

A "semi-regular" grammar is one that only allows rules of the form:

X → y
X → y Y
X → Y y

where X and Y are any single non-terminals, and x and y are any single terminals.

For example, this is a semi-regular grammar for language a+ b+

S → a S
S → a A
A → A b
A → b

Give an example of a semi-regular grammar whose language is NOT a regular language. Be sure to say what the language is and why it is not regular.

1 Answer 1

1

What about

S := aT | -
T := Sb

Note that - represents the empty string; you could replace this with a single terminal symbol if you like, without changing the regularity. This produces the language a^n b^n, the canonical non-regular language. You can easily prove as much using the pumping lemma for regular languages or the Myhill-Nerode theorem.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.