1. (a) Give state diagrams of DFA’s recognizing the following languages. That alphabet is Σ =...

Question

Question

1. (a) Give state diagrams of DFA’s recognizing the following languages. That alphabet is Σ = {a,b}

L1 = {w | w any string that does not contain the substring aab}

L2 = {w | w ∈ A where A = Σ^*− {a, aa, b}}

2. (a) Give state diagrams of DFA’s recognizing the following languages. The alphabet is {0, 1}.

L3 = {w | w begins with 0 ends with 1}

(b) Write the formal definition of the DFA L3.

Answer 1

Answer #1

Answer 2

Similar Homework Help Questions

1.6 Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is...

1.6 Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is 0,1) a. {w w begins with a 1 and ends with a 0)
1. Give a DFA for each of the following languages defined over the alphabet Σ (0,...

1. Give a DFA for each of the following languages defined over the alphabet Σ (0, i): a) (3 points) L={ w | w contains the substring 101 } b) (3 points) L-wl w ends in 001)
1) 2) Give formal descriptions (5-tuples) for the DFAs shown in figure below: 3) Give the...

1) 2) Give formal descriptions (5-tuples) for the DFAs shown in figure below: 3) Give the state diagrams of DFAs recognizing the following languages over ? = {0, 1}: a) LÆ b) L? c) {e, 1001} d) {e, 101, 1001} e) {w : w has prefix 10} f) {w : w does not contain the substring 011} 4) Give the state diagrams of DFAs recognizing the following languages over ? = {0, 1}: a) {w: |w| ? 5} b) {w...

Unless otherwise noted, the alphabet for all questions below is assumed to be Σ (ab). Also...

Unless otherwise noted, the alphabet for all questions below is assumed to be Σ (ab). Also note that all DFA's in your solutions should have one transition for each state in the DFA for each character in the alphabet. 1. (6 marks) This question tests your comfort with "boundary cases" of DFA's. Draw the state diagrams of DFAs recognizing each of the following languages. (a) (2 marks) L = {c) fore the empty string. (b) (2 marks) L (c) (2...
Automata Question. Over the alphabet Σ = {0, 1}: 1) Give a DFA, M1, that accepts...

Automata Question. Over the alphabet Σ = {0, 1}: 1) Give a DFA, M1, that accepts a Language L1 = {all strings that contain 00} 2) Give a DFA, M2, that accepts a Language L2 = {all strings that end with 01} 3) Give acceptor for L1 intersection L2 4) Give acceptor for L1 - L2
1. Construct a DFA that recognizes each of the following languages: a. L1 = {w €...

1. Construct a DFA that recognizes each of the following languages: a. L1 = {w € {a, b}* | w contains at least two a's and at least two b’s} b. L2 = {w € {a,b}* | w does not contain the substring abba} C. L3 = {w € {a, b}* | the length of w is a multiple of 4}

Construct DFA's that recognize the following languages over the alphabet {a,b}: 1. {w|w is any string...

Construct DFA's that recognize the following languages over the alphabet {a,b}: 1. {w|w is any string except abba or aba}. Prove that your DFA recognizes exactly the specified language. 2. {w|w contains a substring either ababb or bbb}. Write the formal description for this DFA too.
Give state diagrams (pictures) for Turing Machines that decide the following languages over the alphabet {0.1}:...

Give state diagrams (pictures) for Turing Machines that decide the following languages over the alphabet {0.1}: 1. {w | w contains an equal number of 0s and 1s} 2. {w | w does not contain twice as many 0s as 1s}.
Give the regular expressions of the following languages (alphabet is ab): a. {w | w has...

Give the regular expressions of the following languages (alphabet is ab): a. {w | w has a length of at least three and its second symbol is a b} b. {w | w begins with an a and ends with a b} c. {w | w contains a single b} d. {w | w contains at least three a's} e. {w | w contains the substring baba} d. {w | w is a string of even length} e. The empty...

Let L1 = {ω|ω begins with a 1 and ends with a 0}, L2 = {ω|ω...

Let L1 = {ω|ω begins with a 1 and ends with a 0}, L2 = {ω|ω has length at least 3 and its third symbol is a 0}, and L3 = {ω| every odd position of ω is a 1} where L1, L2, and L3 are all languages over the alphabet {0, 1}. Draw finite automata (may be NFA) for L1, L2, and L3 and for each of the following (note: L means complement of L): Let L w begins...