Esempio di Prova Intermedia – Informatica teorica (28/03/2024)

D inda 1

MO

O

Indicare V F falsità

la verità delle seguenti

con o :

asserzioni

o

Qualsiasi regolare

sottoinsieme di linguaggio regolare

# è

Q ↑ un .

.

b Un L

linguaggio

v regolare

è regolare

corrisponde

solo un'espressione

se e se a .

~

Una libera (CFG) di

G

dal

grammatica derivazione

contesto l alberi

ha due

LIG

ambigua che

stringa

esiste più

xe

se una o

- .

implementodie regoleerg

ling dei Linguaggi regolan

sottoinsieme e

LELa La

Se regolare

regolare La

allora

è è

e pure

L .

,

Domanda 2 Finito)

Disegnare Deterministico

(Automa =20

DFA a

che che

tutte

minimale contengono

stringhe

le

accetta almeno della

un'istanza

e

un su ,

sotto-stringa .

00 A

% 17

. O

start 91

Po 9t

1

3

Domanda

Disegnare (Automa =20

Finito) 13 contengono

Deterministico stringhe che

DFA le

che tutte almeno

accetta un'occorrenza

e su

un ,

della sotto-stringa della sotto-stringa

11 nessuna

e 000

occorrenza .

O O

00

O D

O 1

start O 1

E O

1

A

1 1 O O

1 110 1100

11 1 A

4

Domanda

la (DFA)

- I formale

Enunciare desizione Deterministici

Finiti

degli Automi

Q -

I e

↑ - .

S Un M

DFA finito

(Q A)

è (insiemel

di finito

Q

quintupla S

S alfabeto

stati

dove è

è Qx

di 8

simboli Q

insieme

una un

90 un :

, ,

, ,

,

, ,

funzione di transizione

la

è di

A

iniziale accettanti

Q

stato

lo

è

E Q stati

è insieme

q e un

, .

i

6 c)

(a

* q e Q

1 q

=

. ,

, AgeQ

a)

5 S(f

ya)

(9 y)

* (p

*

2 = at

. , , ,

, ,

Il linguaggio L(M)

,

M

da

accettato quindi

è :

, 2x

L(M) A]

* ( (q0

* x) + .

= ,

Domanda 5

Dimostrare linguaggi regolari

che chiusi intersezione

sotto

i .

sono

Supponiamo MCQ

linguaggi

che La Di SAL)

MICQ

La Arl

esistono

regolari DFAS da che

i accettano

siamo .

e e qui

conseguenza

, , ,

.

L(Mz) (2)

L

L(M1)

(ossia

(1

rispettivamente e La = e =

Con

Definiamo Mr n. dn An)

DFA

nuovo =

un comi

, ,

,

Qn Qz

Q1 x

· = pz)

(q1

qn =

· ,

<(p Q3

q) eQxQ2 peQ1

An eq =

· = ,

In((p 62(q)

(d1(p)

a)

q) peQ 9eQ2

= per

· at

, ,

,

, ,

Una *. Quindi

(pqle Qnexe

x))

((p (d*

da Lan

(p

semplice x)

pl Ca

che *

x) de

induzione La

mostra ,

perogni e sappiamo

= x

per

, ,

,

, , ,

(x) (x) 8(x)

che XeL

* (Mn) .

(8* (x)

A1 An

definizione

Così

A2 mostra An

di

dalla E e

e . , ,

,

Viceversa S

* (x)

1

(S

(Mn)

, (X) (x)) S(X

An

, S definizione

An Quindi nostra di EA2

EA1

x el che dalla

volta

sappiamo E

se e

ancora una

, ,

. ,

ext(1 nLz .

Domanda 6

Sia (25 is

L

la PC

t

CFG b produzioni

S

, i con :

n

, , ,

, ,

,

, s/b(n)iSSt

S + L eILS

+

la

Scrivere leftmost

derivazione della stringa iblisstbatsnst .

S ibLSS

ibLaSt ibisst

ibLSSS

iSSt StSmSt

ibSSSibiSSSS ibSSSSSt StStSSt

ibris

=>

= > ibisstbSmSt iblisstbatsmst

iblisstbats

iblisstbLntSSt St

=> = .

Domanda 7 P)

la

Sia (E3 41 (3

G E

CFG produzioni

con :

,

, ,

, E EE((E)IE

= "I

Entrambe leftmost

derivazione stringa

della quindi

queste ambigua

la è

grammatica

sono i ,