Question

Question: Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts,$\sum =a,b$.

$$\begin{gathered} \mathbf{\text{a.}}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{\backslash }\mathbf{kern}\mathbf{1}\mathbf{pt}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{three}}\mathbf{ }\mathbf{ }\mathbf{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathbf{b}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{\right\}}\mathbf{}\mathbf{}\mathbf{} \\ \mathbf{\text{b.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{exactly}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{b}\mathbf{\text{'}}\mathbf{\text{s}} \\ \mathbf{\text{c.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{even number}}\mathbf{ }\mathbf{ }\mathbf{\text{of}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{one or}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{b}\mathbf{\text{'}}\mathbf{\text{s}} \\ \mathbf{\text{d.}}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{\backslash }\mathbf{kern}\mathbf{1}\mathbf{pt}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{even number}}\mathbf{ }\mathbf{ }\mathbf{\text{of}}\mathbf{ }\mathbf{ }\mathbf{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and each}}\mathbf{a}\mathbf{\text{is followed by at least}}\mathbf{ }\mathbf{ }\mathbf{\text{one}}\mathbf{ }\mathbf{b}\mathbf{\right\}} \\ \mathbf{\text{e.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{starts}}\mathbf{ }\mathbf{ }\mathbf{\text{with}}\mathbf{ }\mathbf{ }\mathbf{\text{an}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{has at most one}}\mathbf{ }\mathbf{ }\mathit{b} \\ \mathbf{\text{f.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has an odd number of}}\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and ends with a}}\mathbf{ }\mathbf{ }\mathit{b} \\ \mathbf{\text{g.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has even length and an odd number of}}\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{} \end{gathered}$$

Short answer

Answer:

In solution (a),the language L is the result of combiningL₁ and L₂ .

In solution (b),the language L is the result of combiningL₁ and L₂ .

In solution (c), the language L is the intersection of combining L₁ and L₂ .

In solution (d),the machine Mallow the input if and only if both M₁ and M₂ apply it. Because, the language L is the intersection of combining L₁ and L₂ .

In solution (e), be the DFA (Deterministic Finite automata) that recognizes M₁ and M₂ and be the DFAs that recognizes L₁ and L₂ .

In solution (f),the language L₂ accepts the strings that ends with a symbol b .

In solution (g), the language L is the intersection of two simpler languages L₁ and L₂ .

Step-by-step solution

Explain Deterministic Finite Automata

Deterministic Finite Automata is the computational model that has the knowledge of the future states, where the transition takes the current state.

Determine the DFA state diagram of the given language.

a.

Consider the language $L=\left\{w\right|whasatleastthreea\text{'}sandatleasttwob\text{'}s\}$. The language L is formed by combining two simpler languages $L_{1}and{L}_2$.

The languages $L_1=\left\{w\right|whasatleastthreea\text{'}s\}and{L}_2=\{w|whasatleasttwob\text{'}s\}$ are the simpler languages of L₁ and L₂ . Consider that (Deterministic Finite Automata) is the DFA which recognises . Allow M₁ and M₂ to be the DFAs who recognise L₁ and L₂ .

The state diagram of that recognises is as follows,

The state diagram of that recognizes is as follows,

The input will be accepted by machine if and only if both , accept it. Because the language is formed by combining the languages and . As a result, 's state diagram for recognising Language is as follows:

Therefore, the DFA state diagram of the given language has been obtained.

Determine the DFA state diagram of the given language.

b.

Consider the simple languages L₁ = {w|w has exactly two’s} andL₂ = {w|w has at least two b’s}. Consider that the Deterministic Finite Automata (DFA) that identifies and M₁ and M₂ be the DFAs that identifies L₁ and L₂ .

The state diagram of M₁ that recognizes L₁ is as follows,

The state diagram of that recognizes is as follows,

The input will be accepted by machine M if and only if both M₁ ,,M₂ , accept it. Because the language L is the result of combining L₁ and L₂ .

The following is the state diagram of the DFA M ,that recognises L.

Therefore, the DFA state diagram of the given language has been obtained.

The state diagram, can be represented in other way as follows

Determine the DFA state diagram of the given language.

c.

Consider the simple languages, L₁ = {w|w has even number of a’s } and L₂ = {w|w has one or two bs}. Let be the DFA(Deterministic Finite automata) that identified and M₁ and LM₂ be the DFAs that identified L₁ and L₂ .

The state diagram of M₁ that recognizes L₁ is as follows

The state diagram of M₂ that recognizes L₂ is as follows

The machine M will accept the input if and only if both M₁ and M₂ accept it. Because language Lis the intersection of L₁ and L₂ .

The state diagram M of which recognizes the language L is as follows

Therefore, the DFA state diagram of the given language has been obtained

Step 5: Determine the DFA state diagram of the given language

d.

Apply the mathematical language L = { w|w has an even number of ’s and each a is a followed by at least on b }. The language is the inter-part of two easy languages sayL₁ and L₂ .

Now L₁ = { w|w has an even number of ’s } and L₂ = { w|w has each is a followed by at least on b}. Let M be the DFA(Deterministic Finite automata) that recognizes L and M₁ and M₂ be the DFAs that recognizes L₁ and L₂ .

The state diagram of that recognizes M₁ is as follows where L₁ = { w|w has an even number of a’s}.

The state diagram of M₂ that recognizes L₂ is as follows where L₂ = { w|w has each a is followed by at least one b}.

The state diagram M of that recognizes L is as follows

Combine some states to get more simplified form as follows,

Therefore, theDFA state diagram of the given language has been obtained.

Step 6: Determine the DFA state diagram of the given language

e.

Consider the language L= {w|w Start with ana and has at most one b }. The language is the intersection of two simpler languages say L₁ and L₂ . L₁ = {w|w Now starts with } and L₂ ={w|w has at most one }. Let M be the DFA(Deterministic Finite automata) that recognizes L and M₁ and M₂ be the DFAs that recognizes L₁ and L₂ .

The state diagram of M₁ that recognizes L₁ is as follows,

The state diagram of M₂ that recognizes L₂ is as follows.

The machine M will accept the input if and only if both M₁ and M₂ accept it. Because, the language L is the intersection of L₁ and L₂ . The state diagram of M that recognizes L is as follows.

Combine M₁ and M₂ to get more simplified form as follows,

Therefore, the DFA state diagram of the given language has been obtained

Step 7: Determine the DFA state diagram of the given language

f.

Consider the language L has an odd number of ’s and ends with }. The language L is the intersection of two simpler languages say L₁ and L₂ . L₁ = { w|w Now has an odd number of’s} and L₂ = { w|w ends with }. Let be the DFA(Deterministic Finite automata) that recognizes and M₁ and M₂ be the DFAs that recognizes L₁ and L₂ .

The state diagram of M₁ that recognizes L₁ is as follows:

The language L₂ accepts the strings that ends with a symbol b. The state diagram of M₂ that recognizes L₂ is as follows

The machine will accept the input if and only if both M₁ and M₂ accept it. Because, the language L is the intersection of L₁ and L₂ .

Therefore, the DFA state diagram of M the given language L has been obtained.

The state diagram of that recognizes is as follows:

Step 8: Determine the DFA state diagram of the given language

g.

Consider the language L= {w|w has even length and an odd number of ’s }. The language L is the intersection of two simpler languages say L₁ and L₂ . Now L₁ = {w|w has even length } and L₂ = {w|w has odd number of ’s}. Let M be the DFA(Deterministic Finite automata) that recognizes and M₁ and M₂ be the DFAs that recognizes L₁ and L₂ .

State diagram of that recognizes is as follows,

State diagram of that recognizes is as follows

The machine M will accept the input if and only if both M₁ and M₂ accept it. Because, the language L is the intersection of L₁ and L₂ .

The state diagram of that recognize is as follows,

Therefore, theDFA state diagram of the given language has been obtained.