Paths with DFA?

106 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.