# SS Exercise Session Lecture 5

## Exercise 2*

- 1:
$\langle S\rangle \rightarrow \langle Ts\rangle1\langle Ts\rangle1\langle Ts\rangle 1\langle Ts\rangle$
$\langle T\rangle \rightarrow 0 | 1$
$\langle Ts\rangle \rightarrow \langle Ts\rangle\langle T\rangle | \langle T\rangle | \epsilon$

- 2:
$S \rightarrow 1T1 | 0T0$
$T \rightarrow 1T | 0T | \epsilon$

- 3:
$W \rightarrow UWU | 0$
$U \rightarrow 1|0$

- 4:
$S \rightarrow Ø$
Ø er ikke the empty set, Ø er en non terminal

- 5:
$S \rightarrow S | \epsilon$

## Exercise 3*

- 1:
$S \rightarrow 0S1 | 0 | 1 | 0S | S1$
$S \rightarrow $

$S \rightarrow TST|T$
$T \rightarrow 0|1$
S
TST
TTSTT
TTTTT

A -> 0B | 1C | 0 | 1 | 0D
B ->0B1 | 0B | 0 | e
C-> 1 | C1 | e
D ->1 | D1 | e

- 2:
$S \rightarrow Ls | \epsilon$
$Ls \rightarrow L Ls | L$
$L \rightarrow 1L0 | 0L1 | \epsilon$

$S \rightarrow 01 | 10| T$
$T \rightarrow 00U | 11V | S$
$U \rightarrow 11$
$V \rightarrow 00$

- 3:

$ L \rightarrow 0L | L0 | 10 | 01$