Menu
I'm reading through the dragon book and trying to solve an exercise that is stated as follows
Write regular definitions for the following languages:
- All strings of digits with no repeated digits. Hint: Try this problem first with a few digits, such as { 0, 1, 2 }.
Despite having tried to solve it for hours, I can't imagine a solution, beside the extremely wordy
d0 -> 0?
d1 -> 1?
d2 -> 2?
d3 -> 3?
d4 -> 4?
d5 -> 5?
d6 -> 6?
d7 -> 7?
d8 -> 8?
d9 -> 9?
d10 -> d0d1d2d3d4d5d6d7d8d9 | d0d1d2d3d4d5d6d7d9d8 | ...
Hence having to write 10! alternatives in d10. Since we shall write this regular definition, I doubt that this is a proper solution. Can you help me please?
873
A regular expression (regex) defines a search pattern for strings. The search pattern can be anything from a simple character, a fixed string or a complex expression containing special characters describing the pattern.
All strings not ending in 01: + 0 + 1 + (0 + 1)*(00 + 10 + 11). The expression +0+1 describes the strings with length zero or one, and the expression (0 + 1)*(00 + 10 + 11) describes the strings with length two or more.
In that case, a regular expression is (a+b)bbb(a+b). The anatomy of this regular expression is the following: (a+b) gives either "a" or "b" (a+b)* gives any string of "a"s and "b"s whatever.
To match any number from 0 to 9 we use \d in regex. It will match any single digit number from 0 to 9. \d means [0-9] or match any number from 0 to 9. Instead of writing 0123456789 the shorthand version is [0-9] where [] is used for character range.
So the question didn't necessarily ask you to write a regular expression, it asked you to provide a regular definition, which I interpret to include NFA's. It turns out it doesn't matter which you use, as all NFA's can be shown to be mathematically equivalent to regular expressions.
Using the digits 0, 1, and 2, a valid NFA would be the following (sorry for the crummy diagram):
Each state represents the last digit scanned in the input, and there are no loops on any of the nodes, therefore this is an accurate representation of a string with no repeated digits from the set {0,1,2}. Extending this is trivial (although it requires a large whiteboard :) ).
NOTE: I am making the assumption that the string "0102" IS valid, but the string "0012" is not.
This can be converted to a regular expression (although it will be painful) by using the algorithm described here.
113
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
