Problema di espressione regolare

Qual è l'espressione regolare per la lingua 0 ^{m n} dove m + n è pari?Problema di espressione regolare

2010-03-09 erasmus

O io sono stanco o la vostra la domanda ha molto poco senso. –

Non penso che questo abbia qualcosa a che fare con regexp ... –

@Andy E: Non è perché sei un compagno stanco. –

Se vuoi dire una stringa 000...111... in cui la lunghezza della stringa è pari, è possibile utilizzare ^(00)*(01)?(11)*$

fonte

2010-03-09 15:31:07 SLaks

questa non è una risposta perché convalida anche 00 01 1 11 la cui lunghezza non è uniforme. – erasmus

Questo perché ho dimenticato di ancorare la regex. Funziona correttamente ora. – SLaks

+1 per la risposta. Ora, come faccio a votare per capire la domanda in primo luogo? – Amarghosh

Ok, quindi è necessario prendere in considerazione per lo zero i casi in cui ci sono dispari e quando sono ancora. Ciò richiede due stati, uno per zero pari, uno per gli zeri dispari. Quindi per il caso zero zero è necessario avere 1 uno e poi un numero pari di uno. Per il caso pari hai solo bisogno di un numero pari di quelli.

sua facile scrivere il DFA, ma non so come tracciare qui, quindi ho intenzione di tentare di indovinare l'espressione regolare:

(0 (00)* 1 (11)*) \/ (00)*(11)*

fonte

2010-03-09 16:02:08

Qui sono tracciate macchine per quella regex. NFA completo: http://static.max99x.com/misc/nfa.png. NFA pulita: http://static.max99x.com/misc/nfa2.png. DFA ridotto a icona: http://static.max99x.com/misc/dfa.png. –

@Max: fantastico! È uno strumento del tuo design? Ricordo di aver implementato un convertitore NFA su un convertitore DFA minimo molti anni fa, ma non mi è mai venuto in mente di renderlo con graphviz :) –

@ Il-Bhima: Sì. http://max99x.com/school/automata-editor. Potrebbe essere un po 'buggy, però, dal momento che era un progetto scolastico veloce. –

Problema di espressione regolare

risposta

Problemi correlati