Esercizio espressione regolare

[Zarzuf]

Scusate il disturbo. Ho grosse difficoltà a risolvere un esercizio che presumo sia semplice:

Data la seguente grammatica:

S->A|BA
A->11C
B->B0|B1|0|1
C->1B|1

Ricavare l'espressione regolare del complemento del linguaggio ottenuto da questa grammatica.

Presumo che il metodo risolutivo sia:

1)Ottenere l'espressione regolare dalla grammatica
2)Costruire l'automa deterministico
3)Da esso costruire l'automa del complemento
4)Infine ricavare l'espressione regolare

La mia difficoltà al momento è nel punto 1. in quanto non sono sicuro di essere in grado di ottenere un'espressione regolare corretta. Qualcuno ha dei suggerimenti? (so trasformare una grammatica in una espressione regolare generalmente ma quando è un po' troppo complicata ho alcune difficoltà). Grazie in anticipo.

[apatriarca]

Bhe.. Io cercherei invece semplicemente di capire come sia fatto il complemento di quella grammatica. È prima di tutto abbastanza immediato vedere come 'B' sia una qualsiasi successione di 0 e 1 di lunghezza almeno 1. 'C' è invece una successione di 0 e 1 che inizia con un 1. 'A' è infine una successione di 0 e 1 che inizia con tre 1. Riassumendo si ottiene che la grammatica descrive l'insieme delle successioni di 0 e 1 che contengono almeno tre 1 in successione. Il complemento è quindi composto da tutte le successioni di 0 e 1 con al più due 1 in successione. Non resta che costruire una espressione regolare per questo linguaggio.

[Zarzuf]

Grazie mille per la risposta. Ho letto e ho capito praticamente tutto. Ma devo quindi dedurre che non esista un metodo "meccanico" per calcolare il complemento? Devo necessariamente ragionarci su intuitivamente?

[apatriarca]

Non sono la persona giusta per rispondere a tale domanda. Io queste cose le ho viste da solo negli anni e non le ho mai studiate in un corso universitario. Tendo quindi a preferire metodi "intuitivi" e basati sul ragionamento a metodi meccanici (che in molti casi non conosco). Il metodo da te esposto mi sembra abbastanza corretto, però è inutilmente lungo in questo particolare caso.

[Zarzuf]

Gentilissimo e grazie per la disponibilità e la sincerità. Per caso sai dirmi in questo particolare caso un'espressione regolare corretta? (Ci ho provato, anche seguendo il ragionamento che hai esposto, ma non sono molto ferrato con questo tipo di esercizi)

[apatriarca]

Direi che qualcosa tipo (0|10|110)* potrebbe andare bene.

[Zarzuf]

Si ad occhio e croce direi che è un risultato corretto. Vedrò di capire come ci si arriva con un procedimento, ma è già un grande passo avanti. Grazie mille per l'aiuto.