Formális nyelvek gyakorlat (4)

2005. október 13., csütörtök

1. Fogalmazd meg szavakkal, hogy mik az alábbi reguláris kifejezések által leírt nyelvek és adj a reguláris kifejezésekhez determinisztikus véges automatát!:
$0{(0+1)}^*0$,
${(0+1)}^*0{(0+1)}{(0+1)}$,
$0^*10^*10^*10^*$,
${(a+b)}^*(aa+bb){(a+b)}^*$,
${(a^*+b^*)}^*$

2. Add meg reguláris kifejezéssel az alábbi $\Sigma=\{a,b\}$ feletti nyelveket és adj hozzájuk determinisztikus véges automatát:
(a) $\{w\in {\Sigma}^*\;\vert\;$ w-ben van legalább két a$\}$
(b) $\{w\in {\Sigma}^*\;\vert\;$ w-ben minden teljes homogén a-részsorozat páros és minden teljes homogén b-részsorozat páros $\}$
(c) $\{w\in {\Sigma}^*\;\vert\;$ van olyan betű amiből $\geq 2$ van w-ben$\}$
(d) $\{w\in {\Sigma}^*\;\vert\;$ w-ben minden teljes homogén a-részsorozat páros és minden teljes homogén b-részsorozat páratlan $\}$

3. Adj meg egy olyan determinisztikus véges automatát, amelynek nyelve az
$(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le.

4. Döntsük el, hogy az alábbi két reguláris kifejezés által leírt nyelv azonos-e!

$$((a+b) b^* a)^* \quad \quad \mbox{\rm és} \quad \quad (a+b) (b+a(a+b))^* a + \epsilon$$

5. Adjunk determinisztikus véges automatát a $10+(0+11)0^*1$ reguláris kifejezéshez!

6. Mely szavakból áll az a nyelv, amelyet az alábbi reguláris kifejezés ír le:
${(a+b)}^*[aa{(a+b)}^*bb+bb{(a+b)}^*aa]{(a+b)}^*$ ?
Adjunk meg ehhez a nyelvhez egy determinisztikus véges automatát!