Homework

>>202460
>The above image depicts an NFA over the alphabet {p,q,s} with two final states, indicated by double lines.
I don't believe you.

File: p3MLkZB.png (3KB, 255x168px) Image search: [Google]

3KB, 255x168px

>>202463
This is the above image

>>202460
>help with your homework
So what's your question?

>>202483
Just want that problem solved or help on how to solve it.

>>202460
>>202484
Well, first-up, that's like six different problems.

The above image itself has three questions:

- Give three words which are in the language of the NFA, and three which are not.
- In Maths ... Write down the above NFA in this format.
- Suppose we ... which of those would that change the language of the NFA, and if so - give a word that's added to the language.

And then there's this shit on the end:
- Draw equivalent NFAs for the following regular expressions:
- (a|b)(q|b)
- a*b*c*
- (q|ab|def)*

Of the above, which are you having trouble with?

>>202508
The final one

>>202521
The final one is really easy because it lets you use NFAs, which is good for two reasons:

- NFAs are a superset of DFAs, so if there's a bit that writes neatly as a DFA, you can just write it like that.
- you get to use epsilon transitions.

Epsilon transitions are awesome, because they can easily implement* and |.

For *, let's consider a*b*c*. It's like a+b+c+, except there can also be zero as, bs or cs.

So what we do is draw a+b+c+, which is (I'm on my phone, so no drawing for you)
1: a->2
2: a->2, b->3
3: b->3, c->4
(4): c->4

We can then add epsilon transitions from 1->2, 2->3, and 3->4, which changes a+ (one or more as) to a* (zero or more as).

Now |: we just construct each item in the | as a DFA or NFA, and then add a state before them that can transition to the start of every item in the | by an epsilon transition, and an end state that's reachable from all the accepting states by epsilon transition.

So for (q|ab|def), we'd construct three DFAs that recongnised q, ab, and def, and then have a start state that epsilon transitions to the start of each DFA, and and end state that's accepting that is reached from the accepting states of the DFAs by epsilon transition. Then to turn it into (q|ab|def)+, we add an epsilon transition from the last state to the first, and to turn it from (q|ab|def)+ to (q|ab|def)*, we add an epsilon transition from the first state to the last (or we make the first state accepting).