Question

E2 = {[:], [?], [], [1]}. Here, 22 contains all columns of Os and 1s of height two.

a). Provide a DFA M such that L(M) = D, and provide an English explanation of how it works (that is, what each state represents):

b). Prove (by induction on the length of the input string) that your DFA accepts the correct inputs (and only the correct inputs). Hint : your explanation in part a) should provide the precise statements that you need to show by induction. For example, you could show by induction on |w| that

Answer 1

1.

a.

The given language is { w | w contains 011 as a substring }.

This means the string 011 can have any number of 0 or 1 before it as well as after it.

So, the regular expression is :

(0+1)*011(0+1)*

b.

The given language is { w | w is of odd length and there is a 1 in every even position in the string }.

Let the language be divided into 2 parts.

L1 = { w | w is of odd length }

L2 = { w | there is a 1 in every even position in the string }

DFA for L1 is :

ЯА о. 1

DFA for L2 :

30.1

To get the DFA obtained after intersecting the above 2 DFA, the cross product of states have to be applied.

( A, B ) ( C, E, D )

(AC, AE, AD, BC, BE, BD )

The intial state will be AC and the final states will be BC and BE.

To, 1 to 1 AE -0,1 BC BD

After removing the unreachable states AE and BC, the final DFA is :

110, 1

So, the final regular expression of the given language is ( 0+1 ) + ( 0 + 1 )(1(0+1))* = (0 + 1) ( ε + (1(0+1))*).

c.

The given language is { w | w has length atmost 3 or w's length is a multiple of 4 }.

The regular expression for the set of strings having length atmost 3 is :

R1 = ( 0 + 1 + ε ) ( 0 + 1 + ε ) ( 0 + 1 + ε ).

The regular expression for the set of strings having length as multiple of 4.

R2 = ((0+1)(0+1)(0+1)(0+1))*

The required regular expression R = R1 + R2

R = ( ( 0 + 1 + ε ) ( 0 + 1 + ε ) ( 0 + 1 + ε ) ) + ( ((0+1)(0+1)(0+1)(0+1))*).

d.

The given language is { w | w contains exactly two 1s }.

The regular expression for the given language is :

(0)*1(0)*1(0)*.