#include <iostream> #include <cstdlib> #include <set> using namespace std; struct State { int prod, // номер продукции posp, // позиция в продукции poss; // позиция во входной строке // конструктор по значениям полей State(int pr, int p1, int p2): prod(pr), posp(p1), poss(p2) {} }; // вывод состояния ostream &operator <<(ostream &st, State s) { st<<"State("; switch(s.prod) { // продукция P->A case 0: switch(s.posp) { case 0: st<<"P->.A"; break; case 1: st<<"P->A."; break; default: st<<"unknown"; } break; // продукция A->"" case 1: switch(s.posp) { case 0: st<<"A->."; break; default: st<<"unknown"; } break; // продукция A->"0" A "1" case 2: switch(s.posp) { case 0: st<<"A->.0A1"; break; case 1: st<<"A->0.A1"; break; case 2: st<<"A->0A.1"; break; case 3: st<<"A->0A1."; break; default: st<<"unknown"; } break; default: st<<"unknown"; } return st<<", "<<s.poss<<")"<<endl; } // вывод множества состояний, по одному на строке ostream &operator <<(ostream &st, set<State> s) { set<State>::iterator i; for(i = s.begin(); i != s.end(); i++) st<<*i; return st; } // операции сравнения нужны для построения множества bool operator==(State s1, State s2) { return s1.prod == s2.prod && s1.posp == s2.posp && s1.poss == s2.poss; } bool operator!=(State s1, State s2) { return !(s1==s2); } bool operator<=(State s1, State s2) { if(s1.prod < s2.prod) return true; if(s1.prod > s2.prod) return false; if(s1.posp < s2.posp) return true; if(s1.posp > s2.posp) return false; if(s1.poss < s2.poss) return true; if(s1.poss > s2.poss) return false; return true; } bool operator<(State s1, State s2) { return s1 <= s2 && s1 != s2; } bool operator>=(State s1, State s2) { return s2 <= s1; } bool operator>(State s1, State s2) { return s2 < s1; } // максимальная длина обрабатываемой // строки --- 49 символов set<State> S[50]; bool check(char *s) { bool loop; S[0].insert(State(0,0,0)); // начальное значение cout<<"Initial S[0]="<<endl<<S[0]<<endl; int i; // перебираем все позиции входной строки for(i = 0; i == 0 || s[i-1] != 0; i++) { cout<<i<<"-th position============================="<<endl; do // добавляем новые состояния в S[i] { loop = false; // еще ничего не добавлено set<State>::iterator j; set<State> S1; // записываем сюда // новые состояния if(i>0) // применяем правила пункта 2 --- чтение { // перебираем все состояния из S[i-1] for(j = S[i-1].begin(); j != S[i-1].end(); j++) { // если там есть A->.0A1 и вх символ 0 if(j->prod == 2 && j->posp == 0 && s[i-1] == '0') // вставить A->0.A1 S1.insert(State(2, 1, j->poss)); // если там есть A->0A.1 и вх символ 1 if(j->prod == 2 && j->posp == 2 && s[i-1] == '1') // вставить A->0A1. S1.insert(State(2, 3, j->poss)); } cout<<"Added by scanning:"<<endl<<S1; // теперь добавить новые // состояния из S1 в S[i] for(j = S1.begin(); j != S1.end(); j++) if(S[i].count(*j)==0) { S[i].insert(*j); loop = true; // что-то добавлено } S1.clear(); } // применяем правила пунктов 1 и 3 --- // предсказание и завершение for(j = S[i].begin(); j != S[i].end(); j++) { // если в S[i] есть P->.A if((j->prod == 0 && j->posp == 0) || // или A->0.A1 (j->prod == 2 && j->posp == 1)) { // добавить A->. и A->.0A1 S1.insert(State(1, 0, i)); S1.insert(State(2, 0, i)); } // если в S[i] есть A->. if( j->prod == 1 || // или A->0A1. (j->prod == 2 && j->posp == 3)) { set<State>::iterator k; // пробегаем все состояния того // множества, позиция которого указана // в состояниях с A->. или A->0A1. for(k = S[j->poss].begin(); k != S[j->poss].end(); k++) { // если там есть P->.A if(k->prod == 0 && k->posp == 0) // добавляем P->A. S1.insert(State(0, 1, k->poss)); // если там есть A->0.A1 if(k->prod == 2 && k->posp == 1) // добавляем A->0A.1 S1.insert(State(2, 2, k->poss)); } } } // теперь добавить новые // состояния из S1 в S[i] cout<<"Added by prediction and completion:" <<endl<<S1; for(j = S1.begin(); j != S1.end(); j++) if(S[i].count(*j)==0) { S[i].insert(*j); loop = true; } S1.clear(); } while(loop); cout<<"final S["<<i<<"]:"<<endl<<S[i]; } return S[i-1].count(State(0, 1, 0)); } int main() { char s[50]; cin.getline(s, 50); cout<<(check(s)? "yes":"no")<<endl; return EXIT_SUCCESS; }