How do i convert this DFA into a regular expression...

How do i convert this DFA into a regular expression ? I know about the state elimination method but i'm too much of a brainlet to apply it, if someone can help me out

>inb4 look on youtube
I've only found pajeets explaining shit so far.

Attached: DFA.png (760x346, 46K)

Other urls found in this thread:

cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions
twitter.com/AnonBabble

>I've only found pajeets explaining shit so far.

And youll only find pajeets explaining it here because the rest of us don't know more than what phones are hot and whether amd or nvidia stocks are doing better

Convert it to an NFA, then to an RE.

Why would induced non-determinism help here ?

[01]*

Because converting RE to NFA and vice versa is easier than doing and ad-hoc RE -> DFA. And since you can convert any NFA to a DFA, you'll have a reliable method to convert RE -> NFA -> DFA and the other way around.

literally first link from search engine
cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions

Wrong

e|((0|1)*.1)

lol

Attached: 1547225671091.png (346x760, 44K)

>e|
uhh no sweetie

how do i even read this? are the qs states and is the double circled one the beginning part?

create a new final state and point the old final state(s) to it on e
create a new beginning state and point it to the old beginning on e
select any state other than the created ones, call it state p
for every pair q,r of states that aren't the created and the one you just selected, rewrite their arrow as a U bc*d, where a is the arrow between q and r, b the one between q and p, c the loop on p, and d the arrow between p and r
go back to step 3, until there are only 2 states left

this is what i remember, at least

Attached: b467bb.png (821x720, 593K)

qs are states, arrows are transitions, 0s and 1s are events/alphabet, double circle is acceptance state, one way arrow is start state

Can you make a an RE out of that? It accepts an even number of digits that ends with 1.

(0|1)(11|01)*

(00)*(11|01)*

Fuck her right in the pussy, eh?

Kleene star
You can't have the 01 or the 11 case in a kleene star because it accepts zero matches as well.

(00|01|10|11)*(01|11)
Correct answer

this is not even tho?

>correct
>doesnt match 101

1((11)*(0(0)*1)*)*

You probably could make it cleaner

doesn't match 01

(00)*(1|01)((1|00)(00)*(1|01))*
what a abomination, but i don't know how to simplify :^)

the only correct answer is : ((00)+(1+(01))(01)∗(1+(00)))∗(1+(01))(01)∗

To execute REs, we convert them from RE to an NFA with recursion on the RE string, then to a DFA with the powerset construction.
You're going backwards. So you'll have to convert it to an NFA, then apply transformations which merge nodes.
For example, one transformation is to take a node with an edge pointing to itself, and transform it into the same node with no such edge, but a * at the end of its expression.
By the end, you'll have a single node with the RE as its expression.

([01]*0)?(11)*1
This DFA accepts any binary string ending with an odd number of 1s. (11)*1 handles the trailing 1s. ([01]*0)? handles the optional head ending in 0 prefixing the 1s.

TFW can’t find q3