• Non ci sono risultati.

che non includono le sottostringhe ”00”, ”11”

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "che non includono le sottostringhe ”00”, ”11”"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

Automi e Linguaggi Formali Homework 1

Argomenti: [DFA, NFA, -NFA]

1. Sia L il linguaggio che comprende tutte le stringhe sull’alfabeto Σ=0,1,2 che non hanno simboli consecutivi identici. In altre parole, le stringhe in L sono tutte le stringhe in Σ

∗

che non includono le sottostringhe ”00”, ”11”

e ”22”.

. Disegnare il DFA per L (diagramma e tabella delle transizioni δ) . Per ogni stato in δ fornire una breve descrizione del tipo di stringhe

che permettono di arrivare a tale stato.

2. Consideriamo l’automa A descritto dalla seguente tabella delle transizioni:

0 1

→A B B

?B A A

. Quale linguaggio L

A

e’ accettato da A?

. Provare formalmente (per induzione) che A accetta L

A

.

3. Consideriamo l’automa a stati finiti non-deterministico con -transizioni descritto dalla seguente tabella:

a b 

→ A {A,C} ∅ {B}

*B {D} {B} ∅

C ∅ ∅ {D}

D {B} {C,D} ∅

. Ottenere un automa a stati finiti deterministico equivalente

Riferimenti

Scarica adesso ( PDF - 1 pagine - 63.27 KB )

Documenti correlati

QUELLO CHE LE DONNE NON MERITANO

“Gli scatti del calendario non sono certo erotici, e nulla hanno a che fare con la nudità di ben altri calendari in cui l’immagine della donna viene umiliata e involgarita”

TUTTE LE DONNE CHE HANNO RICEVUTO IL NOBEL

[r]

–¥¥ m 0 × ¥ 0 ¥ 1 00 ¥¥

Tali tipi di forme indeterminate si affrontano inizialmente col ricondurle alle forme Nella maggior parte dei casi , poiché vi è un rapporto fra una funzione algebrica e

Non importa che sia lontano.

Elisabetta Sperandeo Progetto Tirocinio IRPET Anno Accademico 2016-2017.. Non importa che

3. a · 0 = 0 per ogni a 2 R 4. ( a) = a per ogni a 2 R 5. a · ( 1) = a per ogni a 2 R

Provare la seguenti propriet` a utilizzando i soli assiomi algebrici dei numeri reali ed eventualmente le propriet` a che la precedono.. Risolvere gli esercizi 1-4 del libro

(1)3 – La programmazione nel linguaggio C Stringhe – 3.8 Stringhe Una stringa `e un vettore di caratteri

Diego Calvanese Fondamenti di Informatica — Corso di Laurea in Ingegneria Elettronica — A.A. ) int isprint(int c); carattere stampabile (incluso lo spazio) int isgraph(int c);

1. Sia DFA A l’automa che rappresenta in linguaggio L che accetta tutte le stringhe in Σ 0,1 che terminano in 011.

Applicare l’algoritmo di riempimento della tabella per identificare le classi di equivalenza in A.... Applicare l’algoritmo di riempimento della tabella per identificare le classi

2 ε = 0 ⟹ 2 σ = 2 σ ⟹ σ = σ σ − σ − σ − σ ' σ S = σ + σ ' S = Q ⟹ σ + σ ' = QS

1) Ricordiamo innanzitutto che in un conduttore bisogna sempre identificare una regione interna, in cui il campo elettrico è nullo. Quindi, indipendentemente dallo spessore