Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My teacher made an example to explain DFA, it was about paths (URL paths), the rules were as follows:

S ::= /
S ::= /O
O ::= [a-z]
O ::= [a-z]R
O ::= [a-z]S
R ::= [a-z]
R ::= [a-z]R
R ::= [a-z]S

Examples of paths could be: /foo, /foo/, foo/bar and so on.

However, I don't understand why you would need the R rules since they are equal to the O rules.

Can I write it without the R? If not, why?

share|cite|improve this question
By DFA, do you mean Deterministic Finite Automata or something else? – Chris Taylor Jun 9 '11 at 21:51
I guess it is However, the way of actually displaying it may be unorthodox in my case. – whirlwin Jun 9 '11 at 21:57
up vote 3 down vote accepted

You don't need them, in fact. The grammar you wrote is equivalent to the one obtained by deleting the R rules and substituting the second O rule by

O ::= [a-z]O

... No idea why your teacher wrote it that way, sorry.

share|cite|improve this answer
@Whirlwin, this is a right regular grammar, a formal grammar having the same expressive power as a DFA. – A. De Luca Jun 9 '11 at 22:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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