COMP2022/2922 Languages and Regular Expressions S2 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP2022/2922 Languages and Regular Expressions
S2 2023
After doing this tutorial you should be able to:
1. design a regular expression given an English specification
2. write an English description of the language of a given regular expression 3. reason and prove results about regular expressions
4. write and justify recursive definitions/processes
Problem 1. Let Σ = {a, b}. Write regular expressions for the following:
1. The set of strings ending in a.
2. The set of strings that have aba as a substring.
3. The set of strings that do not contain ab as a substring.
4. The set of strings of even length.
5. The set of strings with an even number of a’s.
6. The set of strings not equal to ab. (Exam 2022)
7. The set of strings not containing bab as a substring (hard).
Problem 2. Let Σ = {0, 1}.
We use the following shorthand: Σ to mean (0 |1)
Write English descriptions for the language of each of the following regular expressions:
1. Σ∗ 1ΣΣ.
2. (ΣΣΣ)∗
3. (Σ∗0Σ∗ 1Σ∗ ) |(Σ∗ 1Σ∗0Σ∗ ).
4. (1∗01∗01∗0)∗ 1∗
5. (0∗ 10)∗0∗ 110∗ (010∗ )∗ (hard)
Problem 3. Argue that every finite language can be represented by a regular expression.
Problem 4. Give a recursive procedure that decides, given R, if L(R) contains the empty string. You should explain why each case is correct.
Recall the recursive definition of regular expressions: a regular expression is one of ∅, ϵ, a ∈ Σ, (R1|R2), (R1R2), R1(∗) . Hence your procedure should handle these cases separately.
Problem 5. Regular expressions can be used to search text for patterns. How? By solving the membership problem for regular expressions. In this problem you will design an algorithm for this problem (over a fixed alphabet Σ). You will write a recursive procedure Match(R, x) that takes as input a regular expression R over Σ and a string x ∈ Σ∗, and returns 1 if x ∈ L(R), and 0 otherwise.
For instance, say Σ = {0, 1} and R = (0∗ 1∗ ) |(1∗0∗ ). If x = 00111 then the algorithm returns 1, and if x = 001100 then the algorithm returns 0.
1. Provide (high-level) pseudocode for your algorithm and very briefly de- scribe the main idea(s) in plain English.
2. Briefly argue that your algorithm is correct.
Hint: do not worry about finding an algorithm with good complexity (i.e., fast or memory efficient). Just get a correct algorithm. Later in the course we will see how to solve the membership problem in polynomial time. For a history of regular-expression matching see https://www.youtube.com/watch? v=NTfOnGZUZDk
Problem 6. (Assignment Question in 2022)
Let Σ = {a, b}. For each of the following regular expressions, provide a clear and concise English description for the language of that regular expression. No justification is necessary.
1. (a |b)∗ ((aaa)|(bbb))(a |b)
2. b∗ (abb∗ )∗ (a |ϵ)
Problem 7. (Assignment Question in 2022)
Let Σ = {a, b}. For each of the following languages, provide a regular expression for that language. No justification is necessary.
1. The set of strings that contain at most two b.
2. The set of strings that have even length or contain no a, but not both.
3. The set of strings that contain exactly two out of the four length 2 strings (aa, ab, ba, bb) as substrings.
Problem 8. (Assignment Question in 2022) (hard) Give a recursive procedure that decides, given R, if L(R) is infinite. Explain why each case is correct.
Hint: It is likely necessary to design a procedure that obtains and uses some ad- ditional information about the subexpressions beyond whether their languages are infinite. Be very careful with regards to edge cases, such as the empty set.
2023-09-04