2
$\begingroup$

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?

  • 0
    I guess it is http://en.wikipedia.org/wiki/Deterministic_finite-state_machine. However, the way of actually displaying it may be unorthodox in my case.2011-06-09

1 Answers 1

3

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.

  • 1
    @Whirlwin, this is a [right regular grammar](http://en.wikipedia.org/wiki/Regular_grammar), a formal grammar having the same expressive power as a DFA.2011-06-09