Riconoscimento del linguaggio

 

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.

Notice: This work is licensed under a BY-NC-SA. Permalink: Riconoscimento del linguaggio

Comments are closed.