choosing : 1. Draw an NFA for the following regular expression: ----------------

Question

choosing : 1. Draw an NFA for the following regular expression: -----------------> (a.) a(a|b) (b.) (a|b)* (a|b) --------------------------------------------------------------------------------------------------------------------------------------------------------------------- 2. Draw a DFA for the following regular expression: -----------------> (a.) a(a|b)(a|b) (b.) (a*|b*)* --------------------------------------------------------------------------------------------------------------------------------------------------------------------- 3. Perform Top down Parsing for the following grammar: -----------------> S-> AB A-> aA|epsilon B-> b|bB to get the input string

Explanation / Answer

First, a note about terminology: A language is a set of strings over some alphabet. DFAs and NFAs recognize regular languages, not regular expressions. There may be several regular expressions that define the same language. For two languages L1 and L2, if every member of L1 is a member of L2, and vice versa, than L1 and L2 are equivalent. Regarding your first question, the language L1 consists of all strings over {a,b} with at least two 'b's. Language L2 consist of all strings over {a,b} with exactly two 'b's. The string "abbb" is an element of L1 and L3, but not L2. So that leaves L1 and L3 to compare. Any element S of L1 must contain at least two 'b's. Let the first two 'b's in S match the two explicit 'b's in expression E3; then the other components a*, a*, and (a+b)* can always be matched, and S must be in L3. Therefore L1 is a subset of L3. Similarly, any element S of L3 must contain at least two 'b's. Let those match the two explicit 'b's in expression E1; the other components (a+b)*, (a+b)*, and (a+b)* will also have matches, and S is in L1 too. So L1 is a subset of L3, and L3 is a subset of L1, so L1 and L3 must be equivalent. Regarding your second question: use the pumping lemma. Suppose you had a DFA that accepted that language...show that it also must accept strings not in the language, therefore no such DFA can exist. Let S be any string in the language...any substring of S will either have all a's, all b's, or both...so what happens after you "pump" it?

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.