Comprensione della concatenazione, unione e iterazione nella lingua normale

Question

Comprensione della concatenazione, unione e iterazione nella lingua normale

#1 da (2 voti)

1

Sto cercando di capire cos'è un linguaggio normale. Esistono 3 espressioni regolari composte per il linguaggio normale: concat {AB} , unione {A+B} e iterazione {A*} . Quando sono usati in un modo semplice è chiaro per me come operare con loro. Ma sono frustrato da domande come questa:

Find regular language equivalent to: (0 + 1)*1(0 + 1)*
(01 + 11)*(0 + 1)*
(0 + 1)*(10 + 11 + 1)(0 + 1)*
(1 + 0)*1(1 + 0)*
(0 + 1)*(0 + 1)(0 + 1)*

Come capisco che invece di (0 + 1) * può essere "" , la lingua equivalente deve avere almeno 1 e qualsiasi numero di simboli prima e dopo di essa.

(01 + 11)*(0 + 1)* can evaluate to "", wrong
(0 + 1)*(10 + 11 + 1)(0 + 1)* can evaluate to 10 or 11 or 1, can be solution
(1 + 0)*1(1 + 0)* has middle one, can be a solution
(0 + 1)*(0 + 1)(0 + 1)* has (0+1) and can be or 0 or 1 or "", wrong

Le mie ipotesi sono corrette?

regular-expressions languages

posta Viacheslav Kondratiuk 12.11.2014 - 20:55

fonte

1 risposta

Leggi altre domande sui tag regular-expressions languages

Archiviazione efficiente e ricerca multidirezionale di dati gerarchici Git spingere per implementare la tecnica [duplicato]

score 2 · Answer 1

Il linguaggio dato equivale a "qualsiasi stringa di bit con almeno un 1 in esso", quindi le tue ipotesi sono corrette. L'opzione 4 è equivalente perché l'unione è simmetrica, quindi (0 + 1) equivale a (1 + 0) . L'opzione 2 è equivalente perché, tuttavia, si espandono le iterazioni nell'opzione 2, è sufficiente espandere le iterazioni nella regex ancora una volta per compensare la differenza e, al contrario, se si espande entrambe le iterazioni nella regex specificata in "", allora si ottieni solo 1 , che è esplicitamente consentito anche dall'opzione 2.

In generale, provare l'equivalenza equivale a (1) dimostrare che qualsiasi stringa generata da A può essere generata da B e viceversa o (2) trasformando entrambe le espressioni fino a sono identici. Notando che (1 + 0) equivale a (0 + 1) è un'istanza di method (2), argomentando come "puoi sempre scegliere un'iterazione in più" è un'istanza di method (1).