Question

Give regular expressions generating the languages of Exercise 1.6.

a. {begins with a 1 and ends with a 0}

b. { $\mathit{w}\mathbf{|}\mathit{w}$contains at least three 1s}

c. { $\mathit{w}\mathbf{|}\mathit{w}$contains the substring 0101 (i.e., w = x0101y for some x and y)}

d. { $\mathit{w}\mathbf{|}\mathit{w}$has length at least 3 and its third symbol is a 0}

e. { $\mathit{w}\mathbf{|}\mathit{w}$starts with 0 and has odd length, or starts with 1 and has even length}

f. { $\mathit{w}\mathbf{|}\mathit{w}$doesn’t contain the substring 110}

g. { $\mathit{w}\mathbf{|}$the length of $\mathit{w}$is at most 5}

h. { $\mathit{w}\mathbf{|}\mathit{w}$is any string except 11 and 111}

i. { $\mathit{w}\mathbf{|}$every odd position of w is a 1 }

j. { contains at least two 0s and at most one 1}

k. $\left\{\epsilon ,0\right\}$

l. { $\mathit{w}\mathbf{|}\mathit{w}$contains an even number of 0 s, or contains exactly two 1s}

m. The empty set

n. All strings except the empty string

Short answer

DFA is an abbreviation for deterministic finite automata. The consistency of the calculation is referred to as being deterministic. If the machine reads an input string one symbol at a time, the finite automaton is termed a finite-state automaton.

Step-by-step solution

To design the DFA diagram

All the questions are designed to create a clear picture using diagrams and theories.

To Explain the Expression

$$\begin{gathered} 1\left(0+1\right)*0 \\ b.0*10*10*1\left(0+1\right)* \\ c.\left(0+1\right)*0101\left(0+1\right)* \\ d.\left(0+1\right)\left(0+1\right)0\left(0+1\right)* \\ e.0\left(\left(0+1\right)\left(0+1\right)\right)*+1\left(0+1\right)\left(\left(0+1\right)\left(0+1\right)\right)* \\ f.0*+1*+\left(01\right)*+\left(10\right)*+\left(010\right)* \\ g.\left(0+1\right)\left(0+1\right)\left(0+1\right)\left(0+1\right)\left(0+1\right) \\ h.\epsilon +0*+1+111(0+1)+\left(0+1\right)++\left(0+10\right)*11(0+01)+\left(0+01\right)+ \\ i.\left(1\left(0+1\right)\right)*\left(1+\epsilon \right) \\ j.0*\left(00+010+100+001\right)0* \\ k.\epsilon +0l.\left(1*01*01*\right)*+0*10*10* \\ m.\varnothing \\ n.(0+1)+ \end{gathered}$$

Explanation

a. L = w begins with 1 and ends with 0 . Is begins with a=1 and ends with a=0

b. L=w contains at least three 1's. The other side question contains three time is displayed as the minimum time to prove the theory correct.

c. L=w contains sub-string 0101 . Display substring with multiplication/calculation with x and y.

d. L=w has length of at least 3, and the third symbol is 0. In this diagram, there will be a simple basis to identify that the theory of this drawing has proved correct related to DFA.

e. L=w starts with 0 and has odd length, or starts with 1 and has an even length.

f. contains the sub-string 110.

L=w doesn't contain sub-string 110.

g. L= length of w is at most 5.

h. L=w is any string except 11 and 11

i. L = every odd position of w is a 1

j. L=w contains at least two 0's and at most one 1. It's the point where two DFA's meet. The first DFA denotes a language in which the string includes at least two 0s, whereas the second denotes a language in which the string involves something like 1.

The intersection of the two DFAs will be

$L=000*+\left(100+010+000*1\right)0*$In the DFA theorem calculation, based on addition and multiplication counts it.

k. $L=\epsilon +0$Based on this formula, it counts as an addition and the diagram we can see below.

l. $L=w\frac{\Delta y}{\Delta x}$contains an even number of 0's, or contains exactly two 1's

m. DFA accepts all strings. All DFA theory based on the above question is allowed in here. We can see that simple drawing through theory makes it correct.

n. DFA accepts all strings except empty strings.