Applying simplification rules to a DFA to derive a regular expression for it
I'm given this deterministic finite automaton (DFA):
I have to construct a regular expression for it. I do not understand one thing in the method described in my handbook.
First of all, we have to construct steps:
Ā Ā Ā šæ1(š“) = {š}ā šæ2(š“) āŖ {š}ā šæ1(š“)
Ā Ā Ā šæ2(š“) = {š}ā šæ2(š“) āŖ {š}ā šæ3(š“)
Ā Ā Ā šæ3(š“) = {š}ā šæ2(š“) āŖ {š}ā šæ1(š“) āŖ {Īµ}
Then we write it in mathematical notation:
Ā Ā Ā š1 = šš2 + šš1
Ā Ā Ā š2 = šš2 + šš3
Ā Ā Ā š3 = šš2 + šš1 + 1
Eventually, we substitute. In my book, the šæ3 equation is simplified but I cannot figure out how exactly it was simplified...
Ā Ā Ā š3 = šš2 + šš1 + 1 = š1 + 1
What logic/rule did they use to simplify šæ3 into š1 + 1 ?
It is quite straightforward once you see it:
The equation of š1 is right there inside the equation of š3:
Ā Ā Ā š1 = šš2 + šš1
Ā Ā Ā š3 = šš2 + šš1 + 1
Note how the right-hand side of the first equation occurs also in the last equation, so in the last equation you can replace it with š1, giving you:
Ā Ā Ā š3 = š1 + 1
Another way to see is it is to subtract the first equation from the last one (each side of the equation), which gives
Ā Ā Ā š3 ā š1 = 1
...and after you move the negative term to the other side, you have the expected result.
Continuation
After this step, we have:
Ā Ā Ā š1 = šš2 + šš1
Ā Ā Ā š2 = šš2 + šš3
Ā Ā Ā š3 = š1 + 1
and the simplification can continue further. In the second equation we can substitute š3 with its simplified definition, and omit that latter definition:
Ā Ā Ā š1 = šš2 + šš1
Ā Ā Ā š2 = šš2 + šš1 + š
And again we find a similar situation: the righthand side of the first equation occurs in the second one, so we can simplify the second equation:
Ā Ā Ā š1 = šš2 + šš1
Ā Ā Ā š2 = š1 + š
In a next step we can substitute that simplified definition of š2 into the first equation:
Ā Ā Ā š1 = šš1 + šš + šš1
This simplifies to:
Ā Ā Ā š1 = (š+š)š1 + šš
And applying Arden's rule this can be written using the Kleene star as:
Ā Ā Ā šæ1(š“) = (š+š)*šš
In words: any sequence of the symbols š and š that ends in šš.
As a side note: in a programming environment, in regex syntax, you would write it as:
[ab]*ab
- Regular expressions inside SQL Server
- python regex to match multiple words in a line without going to the next line
- Using String's ReplaceAll with regex
- Java - Need some help on a Regex pattern for matching both http and https
- Get Number/Number/Number structure in the given string
- Using regex in Postgres for special characters
- How can I make multiple replacements in a string using a dictionary?
- Regex to *not* match anything
- How to determine where a regex failed to match using Java APIs
- Extract user data using regex from react mention
- How to modify this regex to add up all digits to a number?
- Python Regex match or potential match
- Regex to match copyright statements
- Complex regex pattern for upper plus lower case letters and numbers
- How do I include negative decimal numbers in this regular expression?
- Regex with lookbehind searching for substring
- When transforming a vscode snippet variable, how to substitute a group with nothing?
- Select columns based on string match - dplyr::select
- Java regular expression and escaping meta characters
- Regex Powershell: find a string, then replace nth occurence of another string
- Using Java regex want to match only & but not & < etc
- Replacing multiple blank lines with one blank line using RegEx search and replace
- Using Perl Regex, how can I capture the position of the hyphens in a hyphenated word?
- How to remove square brackets and backticks from a string in Scala using regex replaceAll
- Check if String has only Integers separated by comma in PHP
- Notepad++ replace text with RegEx search result
- Regex match number between 1 and 31 with or without leading 0
- What is the right regex for my String.split()
- Limit repetitions of character to multiple fixed lengths (and not ranges)
- Cannot use boost::regex