Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 en.wikipedia.org/wiki/Deterministic_finite-state_machine. However, the way of actually displaying it may be unorthodox in my case. –  whirlwin Jun 9 '11 at 21:57

1 Answer 1

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|improve this answer
1  
@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

 
discard

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.