Consult the language reference manuals to determine
for each of the following languages:
Describe the languages denoted by the following regular expressions:
In a string of length n, how many of the following are there?
Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexeme is very simple. However, some languages, like SQL, are case insensitive, so a keyword can be written either in lowercase or in uppercase, or in any mixture of cases. Thus, the SQL keyword SELECT can also be written select, Select, or sElEcT, for instance. Show how to write a regular expression for a keyword in a case insensitive language. Illustrate the idea by writing the expression for "select" in SQL.
select -> [Ss][Ee][Ll][Ee][Cc][Tt]
！Write regular definitions for the following languages:
1、
want -> other* a (other|a)* e (other|e)* i (other|i)* o (other|o)* u (other|u)*
other -> [bcdfghjklmnpqrstvwxyz]
2、
a* b* ... z*
3、
\/\*([^*"]*|".*"|\*+[^/])*\*\/
4、
want -> 0|A?0?1(A0?1|01)*A?0?|A0?
A -> 0?2(02)*
Steps:
step1. Transition diagram
step2. GNFA
step3. Remove node 0 and simplify
step4. Remove node 2 and simplify
step5. Remove node 1 and simplify
5、
want -> (FE*G|(aa)*b)(E|FE*G)
E -> b(aa)*b
F -> a(aa)*b
G -> b(aa)*ab|a
F -> ba(aa)*b
Steps:
step1. Transition diagram
step2. GNFA
step3. Remove node A and simplify
step4. Remove node D and simplify
step5. Remove node C and simplify
8、
b*(a+b?)*
9、
b* | b*a+ | b*a+ba*
Write character classes for the following sets of characters:
Note that these regular expressions give all of the following symbols (operator characters) a special meaning:
\ " . ^ $ [ ] * + ? { } | /
Their special meaning must be turned off if they are needed to represent themselves in a character string. We can do so by quoting the character within a string of length one or more; e.g., the regular expression "**" matches the string ** . We can also get the literal meaning of an operator character by preceding it by a backslash. Thus, the regular expression \*\* also matches the string **. Write a regular expression that matches the string "\.
\"\\
The regular expression r{m, n} matches from m to n occurrences of the pattern r. For example, a [ 1 , 5] matches a string of one to five a's. Show that for every regular expression containing repetition operators of this form, there is an equivalent regular expression without repetition operators.
r{m,n} is equals to r.(m).r | r.(m + 1).r | ... | r.(n).r
The operator ^ matches the left end of a line, and $ matches the right end of a line. The operator ^ is also used to introduce complemented character classes, but the context always makes it clear which meaning is intended. For example, ^^{aeiou}*$ matches any complete line that does not contain a lowercase vowel.