Lab 0: Grammars and Formal Languages¶

Theory assignment¶

These assignments are optional for those who need to revise their theory knowledge of regular expressions and formal languages. The lab is intended to make you practice using the basic concepts used in descriptions of formal languages.

Given the alphabet $A = \{ 1, 2, 3 \}$ and the strings x=2, y=13, z=323:
1. What are the strings xz, zyx, z², z⁷; and what are their lengths?
2. What are A¹, A², A⁰?
3. Describe A^* and A⁺.
Given:
Listing 2 Grammar for arithmetic expressions $G(<exp>)$ ¶
```
<exp> ::= <term> | <exp> + <term> | <exp> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= ( <exp> ) | <ident>
<ident> ::= A | B | C ... | Z
```
Listing 3 Example statements in $G(<exp>)$ ¶
```
A*B-C
A*(B-C)
A/B/C
-A*B
```
1. Find derivations and draw a parse tree for the statements in Listing 3.
2. State the handle in statement form <term> * <factor> + B/C
3. State a canonical derivation of one of the statements in Listing 3.
4. Why is A * <exp> * D not in statement form?
5. What are $V$ , $\Sigma$ , and $N$ in this grammar?
6. Describe $\Sigma^+$ and $L(G)$ . State some string in $\Sigma^+$ which is not in $L(G)$ .
Using the grammar in Listing 2, draw the parse tree for the statement:
```
A - <term> * B + ( <term> )
```
Use this to explain why there is no canonical derivation of the statement.
Construct a context-free grammar for even integers which may not begin with zeros (this also applies to a single zero).
provide a regular expression for strings consisting of binary numbers separated by the operators $+$ or $-$ . Example:

10+1001-01 111001

Draw the respective state diagram, too.
Given the alphabet $A = \{ a, b, c, d, e, f, g, h, i \}$ :
1. Construct a context-free grammar for words of one syllable (i.e. words containing exactly one vowel).
2. Construct a context-free grammar for multi-syllable words.
Given the alphabet $A = \{ a, b, c \}$ :
1. Write regular a expression which describes all strings starting with a sequence of zero or several a‘s followed by an arbitrary number of b‘s and c‘s mixed together. The strings finish with another sequence of a‘s. (Example: aaabbcbca, bbca, aa).
2. Can the expression $a^{n}b^{n}c^{n}$ be described using a regular expression? If so, write down the regular expression. If not, motivate why.

Describe the languages (sets) that the following grammars generate: <S> is the start symbol.

```
<S> ::= <A> <A>
<A> ::= 1 <A> 0 | 10
```

<S> ::= 1 <S> 0 | <B>
<B> ::= 0 <B> 1 | ε

<S> ::= 1 <A> | <B> 0
<A> ::= 1 <A> | <C>
<B> ::= <B> 0 | <C>
<C> ::= 1 <C> 0 | ε