Menu
Why regular expression ((x,y)|(x,z)) is nondeterministic as the book "Core Java" said? The author gives his point:
When the parser sees x, it doesn’t know which of the two alternatives to take.This expression can be rewritten in a deterministic form as (x,(y|z))
Could anyone can give me an explanation?
959
Intuitively, a regular expression is deterministic if, when matching a word from left to right with no lookahead, it is always clear where in the expression the next symbol must be matched.
The () will allow you to read exactly which characters were matched. Parenthesis are also useful for OR'ing two expressions with the bar | character. For example, (a-z|0-9) will match one character -- any of the lowercase alpha or digit.
A regular expression is a method used in programming for pattern matching. Regular expressions provide a flexible and concise means to match strings of text. For example, a regular expression could be used to search through large volumes of text and change all occurrences of "cat" to "dog".
The regular expression operators are used for matching patterns in searches and for replacements in substitution operations. The m operator is used for matching patterns, and the s operator is used when substituting one pattern for another.
To have a deterministic form, you are only allowed to have a maximum of one possible way at your current position. Let's say you have a string "x,y". Now the regex engine looks at the first character, the "x". In your expression you have 2 possibilities how your string can go on after an "x" at the first position to accept your input. Next there are 2 ways to check. Either if the string is followed by ",y" or by ",z".
, ⇨ y
⬀
x
⬂
, ⇨ z
For (x,(y|z)) you always have just one way. If an "x" is on position 1 you go to position 2. Same there, just with the ",". Finally he has to check if there is a "y" or a "z" on position 3 to accept the word. There were never 2 ways.
x ⇨ , ⇨ (y or z)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
