Question

Give the finite-state automaton and the regular grammar for the following:

(a) (ab v ba)* v (ab)*

(b) (11*)*(110 v 01)

(c) All strings over {0,1} containing the string 010

(d) All strings over {0,1} which do not contain the string 010

Answer 1

First of all let's understand the questions what they are telling.

1.(ab v ba)* v (ab)*

where 'a' and 'b' are are symbols on which transitions will occur

and 'v' is the symbol of OR

'*' means repetition 0 or more times

So the questions means machine can take

'ab' OR 'ba' any number of times OR only 'ab' any number of times.

For example following strings can be accepted by the machine

abab,ab,ba,babaab.......

So the finite state automation is

where q0 is the initial state and also the final state

and qd is the dead state

Now the regular grammer is

S -> abS | baS |

2.(11*)*(110 v 01)

Now the question is take 11* any time then it takes 110 OR 01 one time

example is 1101, 110,101.....

So the machine is

where q0 is the initial state and q4 and q6 are the final state.

Now regular grammer is

S -> 1A

A -> 0B | 1C

B -> 1D

C -> 0E | 1C

E -> 1F

3.So the question is all the string will contain 010

example

00010,11010,010......

so machine is

So q0 is the initial state and q3 is the final state

this machine stops when 010 will surely contain.

Grammer is

S -> 1S | 0A

A -> 0A | 1B

B -> 0C | 1S

C -> 0C | 1C |

4.Now 4th question is the opposite of 3rd .

So just make the final state as non final and non finals states as final state so in 3rd qurstion final state is q3 so remove that state because there is no need of it as final states will be q0,q1 and q2

So machine will be

so q0 is initial and q0 ,q1 and q2 are final states.

Grammer is

S -> 1S | 0A |

A -> 0A | 1B |

B -> 1S |