CODEWITHSUNDEEP
regexfinite-automataautomatanfa
user3805652
user3805652

Reputation: 67

Design a regular expression or Finite Automata for a language that consists of 01 or 010?

I have tried below question for designing automata but didn't success:

The set of strings that consists of either 01 repeated one or more times or 010 repeated one or more times.

where string contains binary characters only . Please read question carefully . Question taken from Automata Theory Language and Computation by john E.Hopcroft chapter 2.

You can use ENFA(Finite automata with Eplison-Transition) . You can give regular expression too .

Upvotes: 0

Views: 1676

Answers (3)

Mahesh Ch
Mahesh Ch

Reputation: 1

Regular Expression that accepts one or more 01 is :

(0+1)*(01)(0+1)*

And the Regular Expression that accepts one or more 010 is :

(0+1)*(010)(0+1)*

Upvotes: 0

Supriya Sangadala
Supriya Sangadala

Reputation: 1

Here I used epsilon NFA. To construct the finite automata to answer this question.

Here we need to construct the FSM which consists of 01 or 010 repeated one or more times.

The regular expression satisfying the given condition is: (01+010)(01+010)*

The ENFA to this question is designed below:

The ENFA to this question is designed here.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28312

The set of strings that consists of either 01 repeated one or more times or 010 repeated one or more times.

I'm pretty sure I know how to parse this correctly, but will provide notes on how to get the answer for both interpretations I can see (the second interpretation might be a bit of a stretch linguistically, but bear with me). The first parsing I see is this:

The set of strings that consists of either (01 repeated one or more times) or (010 repeated one or more times).

This one's easy; regular expressions are closed under union, which is what the "or" above represents, so we just need regular expressions for the parenthesized parts and we can get the complete expression from those. The subexpressions are easy: repetition is represented by either the Kleene closure (*) or the commonly defined "at least once" operator (+). Following this line of thought, the subexpressions are simply (01)+ and (010)+ and the complete solution is (01)+ + (010)+ (where + has two meanings: used as a unary operator, it's the "at least once" repetition operator, and where used as a binary operator it means union).

The second parsing I see is this:

The set of strings that consist of either 01 (repeated one or more times) or 010 (repeated one or more times).

In other words, we can accept any string formed by repeating either 01 or 010, but we need to use at least one of these. Since we can choose either one to repeat, and since under this interpretation mixing is allowed, we can take (01 + 010)+ as the regular expression.

Again, the first interpretation is almost certainly what is intended, if you copied the question word-for-word.

EDIT: The answer is desired for a third, even less plausible, interpretation: any string, so long as it contains either 01 repeated more than once or 010 repeated more than once.

To get 01 more than once: a = (0+1)* (01) (0+1)* (01)+ (0+1)* To get 010 more than once: b = (0+1)* (010) (0+1)* (010)+ (0+1)* To get either of the above: a + b

To get 01 at least once: c = (0+1)* (01)+ (0+1)* To get 010 at least once: d = (0+1)* (010)+ (0+1)* To get either of the above: c + d

Note: unless you're a native speaker of English and are pretty confident about this interpretation after having discussed it with whomever came up with this assignment, this interpretation is pretty far-fetched - not quite as much as assuming "string" means the stuff cats play with, but getting there.

Upvotes: 1

Related Questions