Université d'Ottawa
SEG-2106 : Software construction
Gregor v. Bochmann
Winter 2008, 2009, 2010, 2011, 2012, 2015

# SEG-2106 - Lab 6

## Part A: Regular expressions and non-deterministic automata

### Exercice 1

We consider the following non-deterministic automaton:

• Describe in English the language accepted by the automaton.
• Construct an equivalent deterministic automaton.

### Exercice 2

We consider the alphabet A={a,b} and the regular expression E=aa(a|b)*a

• Please construct a non-deterministic automaton from this expression using Tompson's algorithm.

### Exercice 3

We consider the alphabet A={a,b} and the regular expression E=(a|b)*(abb|aaa) which defines the language of all words that terminate with abb or aaa.

1. Please construct a non-deterministic automaton from this expression using Tompson's algorithm.
2. Construct an equivalent deterministic automaton.
3. Find the corresponding minimal deterministic automaton.

## Part B: Context-free grammars

### Exercice 4: Construction of a syntax tree

We consider the following grammar:
E --> T | E - T | E + T
T --> SE | T * SE | T / SE
SE --> V | C | ( E )
V --> A | B
C --> 0 | 1 | 2 | 3

Write down a syntax tree for the following expression:
A + ( 2 + B ) / ( 2 * A )

### Exercice 5: Ambiguity

Is the following grammar ambiguous ? - Explain in a few words why it is - or is not.

Grammar (A is the starting symbol) :
A --> a A c | a A | b

### Exercice 6: Ambiguity

Prove that the following grammar is ambiguous:

S --> A B
A --> A id | id
B --> B id | id
id --> a | b | c

### Exercice 7: Generation of sentences

We consider the following grammar:
S --> S a B | A
A --> d A | c
B --> b | A

Which of the following sentences can be generated by this grammar ?

1. cab
2. c
3. cabb
4. caab
5. ccaabb
6. ccaab
7. ddcac

### Exercice 8: Design a grammar

Write down a grammar for the language that consists of all strings formed from the characters a and b that have the same number of a as b. For example, the strings aabb, baba, and aabbababba are part of this language, but not the strings abb, bba, and aabbabb.

Explain why your grammar "does the job".

### Exercice 9: Design a grammar

Write down a grammar that generates exactly all sentences of the following form: A sentence starts with an x which is followed by a certain number of y (at least 2); then there are a certain number of z (possibly zero) followed by one u and a certain number of v; finally there is another x at the end. The number of y must be equal to the number of v.

Explain why your grammar "does the job".

## No lab report required

At the end of the Lab session, please show to the TA your draft texts and diagrams that you prepared for the work items (A) through (D). The TA will take note of the completeness of your work, but will not evaluate the quality of your work.

Please consult with the TA during the Lab session. The role of the TA is to help you to do the work suggested within this Lab.