The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
67 views
How to construct a finite automata equivalent to the regular expression: ( 0 + 1 )* ( 00 + 11 ) ( 0 + 1 )*
asked in Theory of Computation by Loyal (8.6k points) | 67 views
0
You can easily construct a NFA for this which has four states and branches out for 00 and 11.

Then you can convert that NFA to a DFA using the subset construction method.

2 Answers

+2 votes
Best answer

Regular expression says there should be at least 2 consecutive 0's or 2 consecutive 1's.

Construction of finite automata:

Nfa's are usually easy.

1. break down problem and understand requirements. Here we need at least 2 consecutive 0's or 2 consecutive 1's.

2. (0+1)* will accept anything. Whenever you see a '+' try to divide the problem.

Dfa's you can attempt to construct directly for smaller regular expression once you have a good practice.

Here you need to know if 1 is followed by 0 eg. 10 , then you need to keep looking for next immediate(consecutive) 0. Or if you see 0 followed by 1 eg. 01 then you need to search for next immediate(consecutive) 1.

This is not minimum Nfa or Dfa this is just for understanding purpose. You can combine final states to get a minimum one, so in the end both will have four states.

This is a minimized version:

answered by Active (1.3k points)
selected by
+1 vote

Since we have to design nfa we can have choices for inputs.

answered by (275 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,845 questions
47,506 answers
145,764 comments
62,261 users