关键词 > comp2022/2922
comp2022/2922 Tutorial 1 s2 2022
发布时间：2022-08-24
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
comp2022/2922
Tutorial 1
s2 2022
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 E = {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 containing bab as a substring (hard).
Problem 2. Let E = {0, 1}. We use the following shorthands: E instead of (0 | 1), and R+ to mean RR* .
Write English descriptions for the language of each of the following regular expressions:
1. E* 1EE.
2. (EEE)*
3. (E*0E* 1E* ) |(E* 1E*0E* ).
4. (1*01*01*0)* 1*
5. (0* 10)*0* 110* (010* )* (hard)
Problem 3. Let E = {a, b, c}. Which of the languages represented by the follow- ing regular expressions are infinite? Give reasons.
1. a(bc* )
2. (a | b)c
3. (a | b)*
4. O
5. O*
6. e*
Problem 4. Argue that every finite language can be represented by a regular expression.
Problem 5.
1. Show that (R* )* and R* represent the same language.
2. Show that R* and e | RR* represent the same language.
Problem 6. Give a recursive procedure that decides, given R, if L(R) contains the empty string. You should explain why each case is correct.
Problem 7. In this problem you will design an algorithm for solving the mem- bership problem for regular expressions (over a fixed alphabet E), i.e., write a recursive procedure Reg(R, x) that takes as input a regular expression R over E and a string x ∈ E*, and returns 1 if x ∈ L(R), and 0 otherwise.
For instance, say E = {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 complexity. Just get an algorithm that works.
Problem 8. Discuss whether focusing on input strings is a serious restriction to studying computation? For instance, how would you encode an integer as a string? Or a finite set of integers? or a graph? Is there any computational object that we can’t encode as a string?
