# String and Regular Expression

**Topics:**String, Regular expression, Regular language

**Pages:**4 (367 words)

**Published:**October 12, 2014

C term 2014

Solutions of the Sample Problems for the Midterm

Exam

1. Give a regular expression that represents the set of strings over Σ = {a, b} that contain the substring ab and the substring ba.

Solution:

a+ b+ a(a ∪ b)∗ ∪ b+ a+ b(a ∪ b)∗

(20 points)

2. Consider the following grammar G:

S → SAB|λ

A → aA|a

B → bB|λ

(a) Give a leftmost derivation of abbaab.

(b) Build the derivation tree for the derivation in part (1). (c) What is L(G)?

Solution:

1

(a) The following is a leftmost derivation of abbaab:

S

⇒ SAB

⇒ SABAB

⇒ ABAB

⇒ aBAB

⇒ abBAB

⇒ abbBAB

⇒ abbAB

⇒ abbaAB

⇒ abbaaB

⇒ abbaabB

⇒ abbaab

(b)

S

A

S

S

A

B

a

a

B

b

A

b

B

B

a

b

B

(c)

L(G) = a(a ∪ b)∗ ∪ λ

(20 points)

3. Construct a regular grammar over the alphabet Σ = {a, b, c, d} whose language is the set of strings that contain exactly two b-s. Solution:

The following is a regular grammar over {a, b, c, d} whose language is the set of strings containing exactly two b-s:

S → aS | cS | dS | bB

B → aB | cB | dB | bC

C → aC | cC | dC | λ

2

(20 points)

4. Consider the following grammar G:

S → aSA|λ

A → bA|λ

(a) Give a regular expression for L(G).

(b) Is G ambiguous? Explain your answer.

Solution:

(a) The following is a regular expression for L(G):

a+ b∗ ∪ λ

(b) Yes the grammar is ambiguous. Here are two diﬀerent leftmost derviations for the string aabb:

S

and

⇒ aSA

⇒ aaSAA

⇒ aaAA

⇒ aabAA

⇒ aabbAA

⇒ aabbA

⇒ aabb

S

⇒ aSA

⇒ aaSAA

⇒ aaAA

⇒ aaA

⇒ aabA

⇒ aabbA

⇒ aabb

(20 points)

5. Design a DFA that accepts the language consisting of the set of those strings over {a, b, c} in which the number of a’s plus the number of b’s plus twice the number of c’s is divisible by six.

3

Solution:

The state diagram of a DFA is

a,b

q

1

q

2

a,b

a,b

c

c

c

c

c

q0

q3

c

a,b

q

5

a,b

(20 points)

4

q

a,b

4...

Please join StudyMode to read the full document