Question

Regular Languages 4 4 1. Write English descriptions for the languages generated by the following regular expressions: (a) (01... 9|A|B|C|D|E|F)+(2X) (b) (ab)*(a|ble) 2. Write regular expressions for each of the following. (a) All strings of lowercase letters that begin and end in a. (b) All strings of digits that contain no leading zeros. (c) All strings of digits that represent even numbers. (d) Strings over the alphabet {a,b,c} with an even number of a's. (e) Strings over the alphabet {a,b} that contain an odd number of a's or an odd number of b's (or both). 3. For each of the following regular expressions determine which of the strings cc, ababb, bbcab, and ccbbab matches it: (a) (ab) *cla*b*c* (b) (ab|bc*)+ (e) [ab] *cc?(ab)* 4 Lexical Specifications 3 4. Given the string abbbaacc and alphabet {a,b,c} what tokenization will the following lexical specification produce? Token Class Regex 3 b+ ab* ac* 5. Given the string babac and alphabet {a,b,c} what tokenization will the following lexical specification produce? Token Class Regex a(ba) * b*(ab)*

Regular expressions, DFA, NFA, grammars, languages

Answer 1

1.
a)
Strings that have one or more symbols from 0-9 and A-F, and ends with x or X

b)
All strings generated using symbols a and b

2.
a)
a(a|b|...|z)*a

Explanation
stats with a
ends with a
0/more number of lowercase letters in between

b)
0 + (1|2|...|9)(0|1|2|...|9)*

Explanation
0 or starts with 1-9 followed by any digit

--------------------------------------
We are allowed to answer 4 sub parts only. Please post accordingly.