Nella teoria dei linguaggi formali e degli automi, uno dei concetti di base è appunto quello di linguaggio formale, che può essere definito come un insieme di parole, dove ogni parola è una sequenza finita di simboli.
Il problema proposto consiste nel determinare se una certa parola appartiene o meno al linguaggio { 0n1n2n, n >= 1 }, dove i simboli sono 0, 1 e 2.
Questo linguaggio è costituito dalle parole nelle quali il numero di 0 è uguale al numero di 1 e al numero di due.
Inoltre, tutti gli 0 di ciascuna parola devono precedere tutti gli 1 della parola, e questi a loro volta devono precedere tutti i 2.
Ad esempio, la parola 001122 appartiene al linguaggio perché ci sono due 0, seguiti da due 1 e da due 2 (n=2).
La parola 000111122220 non vi appartiene in quanto pur essendoci n=4 occorrenze di ciascun simbolo, uno 0 appare dopo gli 1 e i2.
In modo analogo, la parola 00011112222 non vi appartiene perché il numero di 0 è differente da quello degli altri simboli.
Scrivere un programma che riceve un dato elenco di p parole e stabilisce, per ciascuna di esse, se appartiene al suddetto linguaggio.
Dati di input
Il file input.txt è composto da p+1 righe.
- La prima riga contiene un intero positivo che rappresenta p (p <= 10), il numero di parole da analizzare.
- Ciascuna delle successive p righe contiene una delle parole da analizzare.
- Le parole non sono vuote, e la loro massima lunghezza è di 300 caratteri.
Dati di output
Il file output.txt è composto da p righe.
Nella i-esima riga, deve essere riportata l’indicazione SI se la i-esima parola in input appartiene al linguaggio { 0n1n2n, n >= 1 }, oppure l’indicazione NO in caso contrario.
Esempi
| input.txt | output.txt | |
|---|---|---|
| 1 | 3 001122 0001112222 000111222 |
SI NO SI |
| 2 | 2 0000111122220 012 |
NO SI |
Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.