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 to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}. a. {w w has at least three a's and at least two b's} Ab. {w w has exactly two a's and at least two b's} c. {w w has an even number of a's and one or two b's} Ad. {w w has an even number of a's and each a is followed by at least one b} e. {w w starts with an a and has at most one b}

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 to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}. a. {w w has at least three a's and at least two b's} Ab. {w w has exactly two a's and at least two b's} c. {w w has an even number of a's and one or two b's} Ad. {w w has an even number of a's and each a is followed by at least one b} e. {w w starts with an a and has at most one b}

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Each of the following languages is the intersection of two simpler languages. Ineach part, construct DFAs for the simpler languages, then combine them using theCartesian Product of the two DFAs and produce a final state diagram (reducingthe number of states where possible) for the complete language. Assume thealphabet Σ = {a,b}.a. {w|w has at least 3 a’s and at least 2 b’s}b. {w|w has an even number of a’s and 1 or 2 b’s}c. {w|w starts with an a and has at most 1 b}
L = {am+n bm cn | m,n ≥ 1} over Σ = {a, b, c} A. Design PDA for L (with as less as states possible) B. Is L is regular language? C. Verify it by Pumping Lemma
For each of the following languages L, give a regular expression that represents L and draw or describe a DFA that recognizes L. You do not need to justify your answers. (a) All strings in {0,1}* that do not contain either 100 or 011 as a substring (b) All strings in {0, 1,2}* that do not contain either 01 or 12 or 20 as a substring
. Prove that the intersection of two context-free languages is not necessarily context-free. This is unlike the case of regular languages which are closed under intersections. Hint: Do something similar to what we did on Activity #21 to show something about two of the languages below and then use what we proved in class about the remaining language. Write several sentences to explain your reasoning. L₁ = {ww has the form a"b"c" for some whole numbers n and m} L2 = {ww has the form amb"c" for some whole numbers n and m} L3 = {w|w has the form a"b"c" for some whole number n}
Each of the following languages are composed of two simpler languages over the alphabet Σ = {a, b, c}. For both, construct the DFA’s for the simpler languages, then combine them using the construction of the closure proof:a. {w : w starts with a and has at most one b}b. {w : w has an odd number of b’s or ends in c}
The language A= {w Ew has an even number of 1's} is a regular language over the alphabet { = {0, 1}. Answer the following question: Formally define a DFA with 2 states that recognizes A. a) Draw the state diagram for the DFA. b) Convert the DFA to GNFA. c) Give the regular expression that describes the language A by performing the GNFA reductions procedures discussed in class. IMPORTANT: Show all steps.
Construct a FA(in TG)that accepts the language generated by the RG. A →aB B →abA| b
Given: Language L2 = {w ϵ {a,b}* | w contains substring aab} Construct the DFA representing the given language L2. Assume the layout of the DFA is as follows: ->A->B->C->D*. That is, the number of states are four (4) and A is the starting state and D is the accepting state. What is the next state for the input pair (D,b) in the constructed DFA? A B C D
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to produce a final state diagram for the original language. Assume the alphabet Σ = {a,b}.a. {w|w contains neither the substrings ab nor ba} b. {w|w is any string not in a*b*}c. {w|w is any string not in (ab+)*}
3. Prove that the following languages are either regular or not regular: a. L = {ww contains a "1" six places from the end}, Σ = {0,1} b. L = {ww contains a "1" k places from the end, k ≥ 0}, Σ = {0,1}
Let Cbe the language over {a, b,c, d, e, f} accepting all strings so that: 1.There are precisely two b’s in the string. 2.Every a is immediately followed by an odd number of e’s. 3.Every d is immediately followed by an even number of f’s. 4.e’s and f’s don’t occur except as provided in rules 2 and 3. 5.All a’s occur after the first b. 6.All d’s occur before the second b. 7.In between the two b’s there are exactly twice as many a’s as d’s.HINT: Don’t be intimidated by the number of rules. The way they interact actually helps you simplify the number of cases you have to deal with while constructing this grammar. a. Construct a context-free grammar generating C.Explain how your construction accounts for each rule. b. We could eliminate one rule from Cand make it regular. Which rule would that be, and why would it work? You do not need a formal proof, but you do need an explanation.
Given: Language L2 = {w e {a,b}* | w contains substring aab} Construct the DFA representing the given language L2. Assume the layout of the DFA is as follows: ->A->B->C->D*. That is, the number of states are four (4) and A is the starting state and D is the accepting state. What is the next state for input pair (D,b) in the constructed DFA? A В C D