/*

  Autor: Marcin Jedrzejewski (s1525)
  
  Data: 07-01-2003	
	
  O programie:	

	  Program pobiera gramatyke w postaci normalnej chomskiego oraz zbior slow
	  a nastepnie wypisuje dla kazdego slowa TAK jesli to nalezy do gramatyki oraz
	  NIE w przeciwnym przypadku.
	  Kompilowane pod Microsoft Visual C++ 6.0 oraz pod Red Hatem 8.0 przy 
	  pomocy g++.

  Format danych wejsciowych:

      Gramatyka   := Produkcje
      Produkcje   := Produkcja | Produkcja '\n' Produkcje
      Produkcja   := Nieterminal W '->' W Opis W
      Opis        := X | X W '|' W Opis
      X           := Terminal | Nieterminal Nieterminal 
      Terminal    := { [a-z0-9] } 
      Nieterminal := { [A-Z][0-9]* }
      W           := { [\n ]* - białe znaki } 

   Wiecej o zadaniu:
      http://www.mimuw.edu.pl/~walen/pjwstk/jfa/zadanie2.html
	  
*/

#pragma warning( disable : 4786 )

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <ctype.h>
#include <list>
#include <set>
#include <cassert>
#include <strstream>
#include <fstream>
#include <iomanip>

using namespace std;

enum production_type
{single_terminal, two_nonterminals};

typedef list<string> OpisProdukcji;

//tylko w postaci normalnej chomskiego
struct production {
	string prod_name;
	string opis[2];
	production_type type;
};


typedef list<production> Gramatyka;
typedef list<production>::iterator g_itor;

vector<string> words_to_check;

// funkcje pomocnicze
int IsTerminal(string str);

// glowne funkcje 
void ParseInput(Gramatyka &grammar);
bool CKYAlgorithm(Gramatyka &grammar, string &word);
void PrintGrammar(Gramatyka &grammar);

int main(int argc, char* argv[])
{
	Gramatyka grammar;
	ParseInput(grammar);	

	for (int i=0; i<words_to_check.size();i++)
	{
		bool ret = CKYAlgorithm(grammar,words_to_check[i]);
		if (ret == true)
			cout << "TAK" << endl;
		else
			cout << "NIE" << endl;
	}
	
	//PrintGrammar(grammar);		
	return 0;
}

void ParseInput(Gramatyka &grammar)
{
	string bufor="";
	string tmpstr;
	
	//wrzuc gramatyke do bufora
	//fstream fs;
	//fs.open("words.txt",ios::in);
	while( cin.good() )
	{
	        std::getline(cin,tmpstr,'\n');	
		bufor+=tmpstr+"\n";
		tmpstr="";
	}
	
	//Parsuj wejscie, i umiesc wszystkie produkcje w zmiennej (liscie) grammar
	// typu Gramatyka. Kazda produkcja jest reprezentowana nastepujaco
	// nietermial -> opis1
	// nietermial -> opis2
	//         ...	

	
	string prev_str;			//zbiera elementy opisu (max 2)
	string possible_prod;		//pamieta ostatni znak, ktory moze byc
	// poczatkiem produkcji
	production last_prod;		//aktualnie wypelniana produkcja
	int i=0;
	for(i=0;i<bufor.size();i++)
	{	
		//znaleziono nowa produkcje
		if(bufor[i]=='-' && bufor[i+1]=='>')
		{						
			prev_str="";
			i++;				
			last_prod.prod_name=possible_prod;			
			continue;
		}
		
		//nowy opis aktualnej produkcji
		if(bufor[i]=='|' || bufor[i]=='\n')
		{			
			if( prev_str.empty() ) continue;
			
			last_prod.opis[0]="";
			last_prod.opis[1]="";
			
			int n=0,term=0;
			for(n=0;n<prev_str.size();n++)
			{
				if (isalpha(prev_str[n]) && n>0 )
					term=1;

				last_prod.opis[term]+=prev_str[n];
			}
			if (term==0) 
				last_prod.type = single_terminal;
			else
				last_prod.type = two_nonterminals;
			
			
			grammar.push_back(last_prod);
			prev_str="";
			
			//koniec gramatyki
			if( bufor[i]=='\n' && bufor[i+1]=='\n')
			{
				break;
			}
			else
				continue;
		}
		
		//zbiera opis do string'a
		if(bufor[i]!='\n' && bufor[i]!=' ')
		{
		  if ( isdigit(bufor[i]) )
		      possible_prod+=bufor[i];
		  else
		      possible_prod=bufor[i];
		  prev_str+=bufor[i];
		}
	}//for
	
	int start_pos = i+2;
	int end_pos=i+2;
	string str_copy;
	int num_of_words=0;
	
	
	//wczytaj liczbe slow do sprawdzenia	
	end_pos=bufor.find( '\n',start_pos);
	str_copy = bufor.substr(start_pos,end_pos-start_pos);		
	istrstream(str_copy.c_str(),14) >> num_of_words;
	
	//wczytaj slowa
	while (num_of_words--)
	{
		start_pos=end_pos+1;
		end_pos=bufor.find('\n',start_pos);
		str_copy = bufor.substr(start_pos,end_pos-start_pos);		
		words_to_check.push_back(str_copy);		
	}
}


/*
Wypisuje gramatyke w postaci normalnej chomskiego na standardowe wyjscie
-do poprawnego dzialania wymaga aby gramatyka byla wczesniej posortowana
*/
void PrintGrammar(Gramatyka &grammar)
{	
	Gramatyka::iterator prev_itor=grammar.begin();
	
	for(Gramatyka::iterator itor3=grammar.begin(); itor3!=grammar.end(); ++itor3)
	{
		//wypisz nazwe produkcji, 
		if(prev_itor->prod_name.compare(itor3->prod_name)!=0 ||
			itor3==grammar.begin())
		{
			if(itor3!=grammar.begin())
				cout << "\n";
			cout << (*itor3).prod_name << " -> " ;
		}
		else
		{
			cout <<  " | " ;
		}
		
		//wypisz opis produkcji
		
		cout << itor3->opis[0] << itor3->opis[1];
		
		prev_itor=itor3;
	}
	
	for (int i=0; i<words_to_check.size();i++)
		cout << '\n' << words_to_check[i].c_str();
	
	cout << endl;
}


/*
zwraca :
0 - jesli <e>
1 - jesli terminal
-1 - jesli nieterminal
*/
int IsTerminal(string str)
{
	if (str.compare("<e>")==0)
		return 0;
	
	//jesli np.: "A1", gdzie A1 jest nieterminalem
	if (str.size()>1)
		return -1;
	
	//jesli 'a' | '0' ..
	if (islower(str[0]) || isdigit(str[0])/*(str[0]>='0' && str[0]<='9')*/ )	
		return 1;
	
	return -1;
}

void printtable(set<string> **tab,int d)
{
	string out;
	for (int i=0; i<d; i++)
	{

		cout << i;
		
		for (int j=0; j<d; j++)
		{			
			out="";
			for(set<string>::iterator it=tab[j][i].begin();it!=tab[j][i].end();++it)
				out+=(*it);
			
			cout << "|" << setw(7) << out << "|";
		}
		cout << endl;
	}


}

bool CKYAlgorithm(Gramatyka& grammar,string& word)
{
	int i=0,d;
	set<string> **table; //w komentarzach oznaczana - T
	table = new set<string>*[word.length()+1]; 
	
	for(i=0; i<word.length()+1; i++)
		table[i] = new set<string>[word.length()+1];
	
	
	//najpierw ciagi o dlugosci 1
	for (i=0; i<word.length(); i++)
	{
		//T_{i,i+1}:=\emptyset;
		table[i][i+1].clear();
		
		//for A->a a production of G do
		for(g_itor itor=grammar.begin(); itor!=grammar.end(); ++itor)
		{
			//if a=x_{i,i+1} then T_{i,i+1}:=T_{i,i+1} \bigcup {A}		
			if (itor->type == single_terminal &&
				itor->opis[0].at(0) == word.at(i))
			{
				table[i][i+1].insert( itor->prod_name );
			}
		}
	}//for
	
	

	
	for (d=2; d <= word.length(); d++) //ciagi o dlugosci d >=2		
		for (i=0; i <= word.length()-d; i++) //dla kazdego podciagu o dlugosci d
		{
			//T_{i,i+d}:=\emptyset;
			table[i][i+d].clear();

			//dla wszystkich znakow tego podciagu
			for ( int j=i+1; j<=i+d-1; j++ )
			{
				//dla wszystkich produkcji typu A->BC
				for(g_itor itor=grammar.begin(); itor!=grammar.end(); ++itor)
				{
					if (itor->type != two_nonterminals) continue;
					if ( table[i][j].count(itor->opis[0])==1 &&					
						 table[j][i+d].count(itor->opis[1])==1 )
						 table[i][i+d].insert( itor->prod_name );

				}//for (g_itor...

			}//for(int j..
			
		}//for(i=0...


	//printtable(table,word.length()+1);


	g_itor it = grammar.begin();
	if ( table[0][word.length()].count((*it).prod_name) == 1)
	{
		return true;
	}
	else
		return false;

	for(i=0; i<word.length(); i++)
		delete[] table[i];
	delete[] table;
}