Regular Expression

Question

I have a grammar defined as follows:

A -> aA*b | empty_string

Is A a regular expression? I'm confused as to how to interpret a BNF grammar.

Answer 1

A appears to be a BNF grammar rule. I'm not really sure why you have this confused with a regular expression. Are you confused because it has a * in it? Everything that has a * isn't a regular expression.

Answer 2

No, this question doesn't actually have to do with regular expressions. Context-free grammars specify languages that can't be described by regular expressions.

Here, A is a non-terminal; that is, it's a symbol that must be expanded by a production rule. Given that you only have one rule, it is also your start symbol - any production in this grammar must start with an A.

The production rule is

(1)    A -> aA*b | 
(2)         empty_string

a and b are terminal symbols - they are in the alphabet of the language, and cannot be expanded. When you have no more nonterminals on the left-hand side, you are done.

So this language specifies words that are like balanced parentheses, except with a and b instead of ( and ).

For instance, you could produce ab as follows:

A -> aA*b (using 1)
aAb -> ab (using 2)

Similarly, you could produce aabb:

A -> aA*b (1)
aAb -> aaA*bb (1)
aaAbb -> aabb (2)

Or even aababb:

A -> aA*b
aA*b -> aabA*b:
aaba*b -> aababA*b:
aababA*b: -> aababb

Get it? The star symbol may be a bit confusing because you have seen it in regular expressions, but actually it does the same thing here as there. It is called a Kleene-closure and it represents all words you can make with 0 or more As.

Answer 3

Regular Expressions generate Regular languages and can be parsed with State Machines.

BNF grammars are Context Free Grammars which generate Context Free languages and can be be parsed with Push Down Automata (stack machines)

Context Free Grammars can do everything Regular Grammars can and more.