2

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?

whirlwin
  • 123
  • By DFA, do you mean Deterministic Finite Automata or something else? – Chris Taylor Jun 09 '11 at 21:51
  • 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. – whirlwin Jun 09 '11 at 21:57

1 Answers1

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.

A. De Luca
  • 424