Semplifica questa espressione regolare

Sto facendo alcuni esercizi di pre-esame per la mia classe di compilatori e ho avuto bisogno di semplificare questa espressione regolare.Semplifica questa espressione regolare

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Abbastanza ovviamente, la e è la stringa vuota e U sta per unione.

Finora, penso che uno dei (a U b) * possa essere rimosso, come l'unione di un U a = a. Tuttavia, non riesco a trovare altre semplificazioni e non sto andando così bene con gli altri problemi finora. :(

Ogni aiuto è apprezzato, grazie mille!

fonte

2011-02-10 CompilersBeginner

Preferisco molto le spiegazioni a qualsiasi risposta, o anche suggerimenti piuttosto che risposte, sto facendo esercizi di pre-esame, le risposte senza spiegazioni non mi aiuteranno molto! Grazie! – CompilersBeginner

Credo che la mia risposta accettata sia errata, come sottolineato nei commenti. Penso che il risultato sia davvero (a U b) * ma la mia spiegazione non è corretta. – Piva

po 'arrugginito su regex, ma se ancora * rappresenta la "zero o più occorrenze" si può sostituire:

(a U e)b* for (a U b)*

che lascia la prima parte con:

(a U b)*(a U b)* = (a U b)*

Sul lato destro, è necessario che

(b U e)a* = (b U a)*

Ora, dal momento che un U b = b U una, si ottiene:

(a U b)*(a U b)*

sul lato destro della strada, che lascia appena

(a U b)* U (a U b)* = (a U b)*

io credo che sia così ...

fonte

2011-02-10 01:59:58 Piva

Oh mio Dio, mi fa male la testa perché anche la mia espressione è arrugginita. Potresti avere ragione, ma * cosa è successo al token 'e' *? Non vedo come viene eliminato. Ma potrebbe essere possibile che io non lo veda (di nuovo, età e mancanza di caffè combinate con regex rustiness.) –

Il primo passo è sbagliato, poiché il primo consente solo 1 'a' e solo nella prima posizione. –

@BoltClock: non c'è 'a?' Nella risposta che vedo. –

penso che il tutto è equivalente a (a U b)* (o nella maggior parte delle grammatiche regex, (a|b)*)

fonte

2011-02-10 01:56:01

Dato che sto facendo problemi di pratica per un esame, sono molto più interessato a come sei arrivato a questa conclusione. Potresti condividerlo? – CompilersBeginner

Ecco il mio ragionamento: guarda il ramo sinistro dell'unione superiore. Per prima cosa prendi '(a U b) * (a U e)'; distribuire la concatenazione attraverso l'unione per ottenere '(a U b) * a U (a U b) *'. La seconda parte è un superset della prima, quindi collassa in '(a U b) *'. Aggiungere il 'b *' alla fine fa la stessa cosa: tutto ciò che è abbinato da '(a U b) * b *' sarà anche abbinato a '(a U b) *' e viceversa. Ciò rende la RE in '(a U b) * U (a U b) * (b U e) a *'; dato che il lato destro può accettare solo stringhe di 'a' e' b', è un sottoinsieme del lato sinistro, quindi il RE semplifica semplicemente '(a U b) *'. –

@CompilersBeginner: Due forme sono equivalenti se la corrispondenza tra il primo e il secondo implica la corrispondenza del secondo, e il secondo corrisponde al primo, giusto? La tua espressione non introduce mai token tranne 'a' e' b', quindi qualsiasi cosa che corrisponda ad essa corrisponde anche a '(a U b) *'. E qualsiasi '(a U b) *' corrisponde al tuo prendendo il primo ramo, '(a U b) * (a U e) b *', quindi scegliendo il ramo stringa vuota '(a U b) * eb * ', e infine scegliere il conteggio della ripetizione 0 per' b * '. –

Prima tran ardesia di una descrizione in inglese del linguaggio:

(a U b)*(a U e)b* U (a U b)*(b U e)a*

si traduce in:

Qualsiasi sequenza di a s o b s, seguita eventualmente da un a, seguita da un numero qualsiasi di b s .

Qualsiasi numero di a s e b s, seguita eventualmente da un b, follwed da qualsiasi numero di a s

Ci sono un sacco di sovrapposizione qui - almeno (a U b)*(a U e) è esattamente come (a U b)*, perché "Qualsiasi sequenza di a s e b s" necessariamente sia termina con a o epsilon (come qualsiasi stringa può terminare con epsilon) così quei gruppi possono essere eliminati, lasciando

(a U b)*b* U (a U b)*a*

traduce:

Qualsiasi sequenza di a s o b s, seguita da un numero qualsiasi di b s .

Qualsiasi numero di a s e b s, follwed da qualsiasi numero di a s

Ora la prima sezione di coloro ai gruppi più esterni è lo stesso, così lascia crollare quelle in uno

(a U b)*(a* U b*)

si traduce in:

Qualsiasi sequenza di a s o b s, seguita da un numero qualsiasi di a s o con qualsiasi numero b s.

ora aspetta un minuto, "Qualsiasi sequenza di As e Bs" necessariamente termina con "Qualsiasi sequenza di a s OR qualsiasi sequenza di b s", che significa qualche cosa che corrisponde alla prima parte può corrispondere tutto regolare (perché la seconda parte può avere una lunghezza pari a zero) così perché non ci rendono solo

(a U b)*

Ta Da. Semplice.

fonte

2011-02-10 02:01:18 tobyodavies

Secondo il tuo ragionamento (a U b) * b si ridurrebbe allo stesso modo ... ma non lo è. Devi assicurarti che non tutte le corrispondenze continuino a corrispondere, ma che tutti gli input rifiutati siano ancora respinti e il tuo argomento non ha rispettato il secondo. –

@ Ben Quale passo perde informazioni? Molte delle semplificazioni si basano su tutti i bit finali che possono avere lunghezza 0, che il tuo esempio non è così non sono sicuro di ciò che stai riferendo. – tobyodavies

@Ben, io _think_ ti riferisci ai miei 1 o 3 passi in cui dico che poiché la prima ripetizione _necessariamente_ termina con il secondo possiamo rimuovere il secondo, che di nuovo non si applica al tuo esempio - '(a U b)' non _necessarily_ termina con un 'b' - potrebbe finire in' a' quindi la semplificazione non si applica. – tobyodavies

I'll darvi un'idea di come avrei risolverlo: (non molto formale e nessuna garanzia)

Guardate il lato sinistro della U principale:

(U b) * - Cosa significa? Una combinazione di A e B di lunghezza n, dove n> = 0.

Avanti viene (a U e). Cosa abbiamo qui? Una parola a o vuota. Se lo volessimo, avremmo potuto averlo già nella parte precedente. Se vogliamo la e, beh, possiamo lasciarla comunque. Si prega di notare qui che non dobbiamo prendere un a, perché abbiamo la possibilità di scegliere e. Quindi possiamo saltare questa parte intera.

Qual è il prossimo? b *. Cos'è quello? Come molti come vogliamo. Avremmo potuto ottenere anche quelli nella prima parte! possiamo lasciarlo fuori!

Quindi l'unica cosa a sinistra è (a U b) *.

Diamo uno sguardo sul lato destro:

Ok questo è facile ora, possiamo usare la stessa idea è solo lettere diverse.

Avremo anche (a U b) * allo stesso modo.

Quindi alla fine abbiamo (a U b) * U (a U b) * che tu sai è uguale a (a U b) *.

fonte

2011-02-10 02:06:31 FabianB

Secondo il tuo ragionamento '(a U b) * b' si ridurrebbe allo stesso modo ... ma non lo è. –

Grazie per il suggerimento, stavo cercando di dare un approccio meno formale nella mia risposta. Non sono sicuro di come migliorare la risposta senza rinunciarvi. – FabianB

Semplifica questa espressione regolare

risposta

Problemi correlati