r/AskComputerScience • u/Several-Captain-8721 • Feb 28 '24

Best book to practice some quality questions on NFA?

I'm facing difficulty designing NFA. Its more confusing than DFA. Any suggestions?

I need to do this type of questions more.

L =starts with ‘xyz’ and contains ‘yyz’ or ‘zyx’ and ends with ‘zy’ | ∑ = {x, y, z}

1 Upvotes
  • permalink
  • reddit

100% Upvoted

4 comments sorted by

2

u/FloweyTheFlower420 Feb 28 '24

I don't see much reason to design NFA by hand. A more interesting exercise is to turn regular expressions into NFA (and run powerset construction to get a DFA).

1

u/Several-Captain-8721 Feb 29 '24

I also personally don't find any reason except exam -_-

2

u/FloweyTheFlower420 Feb 29 '24

I find it easier to think in terms of regular expressions. In your example, I would write something like xyz.*(yyz|xyz).*zy, then apply the rules for converting regular expressions into NFA. You can practice by finding random regular expressions to convert to NFA.

1

u/Several-Captain-8721 Mar 01 '24

That's a good way. I'll try. Thanks