// Example 13.7. Program to determine if strings are in the
// language with grammar rules S -> 0, S -> 1, S -> 0S, S -> 1S

#include <iostream> 
#include <string>

using namespace std;

int main()
{
   bool inLanguage(const string& s);
   
   string s;
   
   cout << "This program determines if strings are in the\n";
   cout << "language with rules S -> 0, S -> 1, S -> 0S, S -> 1S\n\n";
   
   cout << "Type a string (return to end): ";
   getline(cin, s);
   while (s != "")
   {
      if (inLanguage(s))
         cout << s << " is in the language\n\n";
      else
         cout << s << " is not in the language\n\n";
      cout << "Type a string (return to end): ";
      getline(cin, s);
   }   
   
   return 0;
}   

//
// Example 13.7. Boolean function to return true if a string is
// in the language which has the following grammar rules:
// S -> 0, S -> 1, S -> 0S, S -> 1S
// Pre:  s is a string.
// Post: true has been returned if s is in the language,
//       false otherwise.
//

bool inLanguage(const string& s)
{
   bool recognize;   // boolean return value

   if (s[0] == '0' || s[0] == '1')
      if (s.length() == 1)
         recognize = true;
      else
         recognize = inLanguage(s.substr(1, s.length() - 1));
   else
         recognize = false;

   return recognize;
}