Jump to content

DFA that accepts ab or ba is accepting abba as well, is this correct? How?

Featured Replies

image.png.751cfa50d45b4824dd3d199c5ec2f17d.png

This dfa accepts abba as well. I know this is correct as this is from reputed source, but I can't wrap my head around how is this correct. Please guide me.

Trying to provide a hint*, assuming I understand the problem:
-It may help to look at different parts of the DFA in isolation and what each part contribute.
-You can try to apply one specific example to the DFA and check want comes out.

Let's try the second case using "abba". As "a" is entered as input to the DFA, the upper path will be followed. Can you figure out what happens for the next character in "abba", the first "b"? Do we progress to a new state or stay in the same state?

 

*) no complete answer since this is homework section

 

Please sign in to comment

You will be able to leave a comment after signing in

Sign In Now

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.