CMSC 330: Regular Expression and Finite Automata PracticeProblems1. For each of the following regular expressions, write down three strings in the language generated bythe expression, and give a short English description of the language. AssumeP= {0, 1}.(a) 0+(0 ∪ 1)1+(b) 0*10*10*10*(c) 0*(100*)*1*(d) ( 0 ∪ 10 )*1( 1 ∪ 10 )*2. Consider sets of binary strings A = {0, 00, 000} and B = {11}. Show the language denoted by each ofthe following:(a) A0(b) A1(c) A ∪ A2(d) AB2(e) (AB)2(f) B3(g) A∗(h) (A ∪ B)23. For each of the following problems construct a deterministic finite automaton which describes or rec-ognizes the language given. The underlying alphabet isP= {0, 1}. Be sure to give DFAs and notNFAs. Do not use any notational conveniences or shortcuts given in lecture.(a) { w | w begins with 01 and ends with 01. }(b) { w | w has an even number of 1’s. }(c) { w | w has two or three 1’s. }(d) { w | w has an even number of 0’s, and |w| is even. }(e) { w | w has an even number of 0’s and odd number of 1’s. }1(f) { w | w contains the substring 110. }(g) { w | w does not contain the substring 110. }(h) { w | w does not contain neither of the substrings 11 and 00. }(i) { w | w has exactly one occurence of the substring 010. }(j) { w | w has n occurences of 0’s where n mod 5 is 3. }4. For each of the following problems, assumeP= {a, b}.(a) Convert the following NFA to a DFA.(b) Write a regular expression that accepts the language defined by 4a.(c) Conver the following NFA to a DFA.(d) For each of the following strings, determine whether it is recognized by 4c or not.i. babii. aababbbiii. aabbaaaaiv. aabaaav. bbaabbab2vi. aabba5. Construct a NFA that accepts C-like comment delimited by /* and */. Do not handle nested comments(assume they are not allowed). For simplicity, useP= {/, ∗, c} where c is the only (non-comment)character in the language. Then, Write a regular expression for the NFA you contructed.6. Let L be a regular language. Prove that R(L), strings in L reversed, is also a regular
View Full Document
Unlocking...