Assignment1

Assignment 1

11713020

张佳晨

Exercise 1

When a C compiler compiles the following statement, how many tokens will it generate? [5 points]

int a3 = a * 3;

It should be 7 tokens. (1 keyword, 3 id, 1 =, 1 *, and 1 termination ; )

Exercise 2

In a string of length n(n >0), how many of the following are there?

1. Prefixes [5 points]
2. Proper prefixes [5 points]
3. Prefixes of length m(0< m≤n) [5 points]
4. Suffixes of length m(0< m≤n) [5 points]
5. Proper prefixes of length m(0< m≤n) [10 points]
6. Substrings [10 points]
7. Subsequences [10 points]

1. n + 1
2. n - 1
3. 1
4. 1
5. When m < n, it's 1. When m = n, it's 0.
6. (1+n)*n/2 + 1
7. 2^n

Exercise 3

Describe the languages denoted by the following regular expressions:

1. All strings consisting of a and b.
2. All strings consisting of a and b, and the last third digit is a.
3. Using any length of string which consists of only a to split the string bbb(any can be at the both end).

Exercise 4

Write regular definitions or regular expressions for the following languages.

1. All strings representing valid telephone numbers in Shenzhen. A valid telephone number contains the country code (86), a hyphen, the area code 0755, another hyphen, and eight digits where the first one cannot be zero (e.g., 86-0755-88015159). [10 points]
2. All strings of a’s and b’s that start with a and end with b. [10 points]
3. All strings of lowercase letters that contain the five vowels in order. [10 points]

1. 86-0755-[1-9][0-9]{7}

2. a(a|b)*b

3. letters_ -> [b-df-hj-np-tv-z]*
   letters_aletters_eletters_iletters_oletters_uletters_
   

Optional Exercises 1

Suppose we have a alphabet Σ ={a,b,c}, write regular definitions to describe all strings over Σ without repeated letters.

[Hint: You may draw an NFA for the language and convert the NFA to regular definitions.]

(a(bc|cb))|(b(ac|ca))|(c(ab|ba))|(a(b|c))|(b(a|c))|(c(a|b))|(a|b|c)

Enumerate all possible strings with different with regex:

1. For length 3: (a(bc|cb))|(b(ac|ca))|(c(ab|ba))
2. For length 2: (a(b|c))|(b(a|c))|(c(a|b))
3. For length 1: (a|b|c)