Regular Grammar Inequivalence

This one seems almost too simple to be worth a post.  But here it is for completeness.

The problem: Regular Grammar Inequivalence.  This is problem AL14 in the appendix.

The description: Given two regular grammars G1 and G2, where each production has the form A->a or A->aB (where “a” is a terminal symbol and “A” and “B” are non-terminals), do G1 and G2 represent different languages?

Example:

Suppose G1 was:

  • S->aA
  • A->aA | bA | a | b

(That’s a grammar for “all strings over {a,b} starting with a”)

Suppose G2 was:

  • S->aS | bS | a

(That’s a grammar for “all strings over {a,b} ending with a”)

Since G1 can produce “ab” and G2 can’t, the grammars are inequivalent.

Reduction:

This seems to me to be a very simple restatement of Regular Expression Inequivalence.  Since we can easily turn a regular expression into a regular grammar (see, for example, the first hit I got when I googled “Convert regular expression to regular grammar”, which actually does a pretty good job of showing you how it works: ), then any pair of regular expressions can be expressed as a pair of grammars that is inequivalent if and only if the original expressions are.  Am I missing something?

Difficulty: 3, though I guess it depends on whether your students know how to go between regular expressions and regular grammars.

Leave a Reply

Your email address will not be published. Required fields are marked *