Question

This project is intended to increase your understanding of languages and grammars. In a regular grammar (RG), all production rules must have one of the following forms:

                        N_i = t₁t₂t₃...t_kN_j

N_i = t₁t₂t₃...t_k

where t_i denotes a terminal (alphabet symbol), and N_j and N_j denote nonterminals. Any language defined by a regular grammar is a regular language. Regular languages can also be defined by finite automata, transition graphs, and regular expressions.

More complex grammars, such as context-free grammars (CFG), can define additional languages beyond regular languages. In a context-free grammar, the production rules have the form:

                        N_i = any string of terminals and nonterminals

where N_i denotes a nonterminal. Any language defined by a context-free grammar is a context-free language. Regular languages are a proper subset of the set of all context-free languages.

Part A

Write a CFG class that meets the following design specifications:

Instance variables:

String[] Code           -- production rules as program code

char     startNT        -- starting nonterminal

Constructor:

CFG(String[] C)

Methods:

     char getStartNT()

     void setStartNT(char stNT)

     boolean processData(String inString, String wkString)

The CFG class includes an instance variable Code of type String. The Code array contains program statements that define the production rules for the grammar. The instruction format for a CFG is:

     LHS=>RHS

where LHS is the left-hand side and RHS is the right-hand side of a production rule. For a CFG, the LHS character is a single nonterminal. The RHS string can contain both terminals and nonterminals. For example, the statement S=>aTa, with LHS = S and RHS = aTa, states that S can be replaced by aTa.

It is assumed that the starting nonterminal is the LHS value for the first production rule. The setStartNT method can be used to change the starting nonterminal.

Note that you will need a recursive algorithm for the processData method, since two production rules may have the same LHS value. Your CFG class should work for the sample test program you will be given. Turn in the source code for your CFG class.

Part B

Define a context-free grammar for each of the languages described below. Then write a test program to implement the grammar as an instance of your CFG class. Each context-free grammar should be defined in a separate test program.

1.     A CFG for alphabet {a,b} that recognizes the language consisting of all strings that start with an odd number of a's followed by the same number of b's. Test your program with the following input strings:

                        ab, aabb, aaabbb, aaabbbbb, aaaabbb

2.     A CFG for alphabet {a,b} that recognizes the language consisting of all strings of length 1 or greater that do not contain the substring aa. Test your program with the following input strings:

                        abba, abbabaaa, abaabab, bababbab, bbbabba

3.     A CFG for alphabet {a,b} that recognizes the language consisting of all strings that contain exactly one b, have 2N a's (N >= 0, N is an integer) before the b, and 2N+1 a's after the b. Test your program with the following input strings:

                        ba, aaabaaaa, aabaaa, abaa, aaaabaaa

4.     A CFG for alphabet {x,y,z} that recognizes the language consisting of all strings that start with z, followed by N x's (N >= 0), followed by twice as many y's, and ending with z. Test your program with the following input strings:

                        zz, zxxyyz, zxxyyyy, zxyyz, zxxyyyyz

For each context-free grammar in Part B, turn in your definition of the grammar, the source code for the test program, and the output for the test input strings.

Sample test program for CFG class

// Test Context-Free Grammar Class

import java.io.*;

public class TestCFG

{

   public static void main(String[] args)

   {

      // Language: strings that contain 0+ b's, followed by 2+ a's,

      // followed by 1 b, and ending with 2+ a's.

      String[] C = {"S=>bS",

                    "S=>aaT",

                    "T=>aT",

                    "T=>bU",

                    "U=>Ua",

                    "U=>aa"};

      String inString, startWkString;

      boolean accept1;

      CFG CFG1 = new CFG(C);

      if(args.length >= 1)

      {

         // Input string is command line parameter

         inString = args[0];

            char[] startNonTerm = new char[1];

         startNonTerm[0] = CFG1.getStartNT();

            startWkString = new String(startNonTerm);

         accept1 = CFG1.processData(inString, startWkString);

         System.out.println(" Accept String? " + accept1);

      }

   } // end main

} // end class

Answer 1

SOLUTION :

CONSIDERING THE CONDITIONS AND REQUIREMENTS FROM THE QUESTIONS

HERE CODE :

import java.util.Arrays;
public class Part_A_CGF {
//Instance variables:
private final String[] Code;// -- production rules as program code
private char startNT; // -- starting nonterminal

//Constructor:
Part_A_CGF(String[] C){
Code = C;
startNT = C[0].charAt(0);
}

//Methods:
public char getStartNT(){
return startNT;
}
public void setStartNT(char stNT){
startNT = stNT;
}
// wkSting is work string (build from production rules)
public boolean processData(String inString, String wkString){
//System.out.println("insring: "+ inString + " wkString: " + wkString);
//If inString and wkString are equa then return true
if(inString.equals(wkString))
return true;
//If wkString is larger than inString then return false
if(inString.length() < wkString.length()-2)
return false;
//Search for a nonterminal (Upper Case character) in wkString
int dex;
String NonTerm = "";
int len = wkString.length();
for(dex = 0; len>dex; dex++){
if(Character.isUpperCase(wkString.charAt(dex))){
NonTerm = Character.toString(wkString.charAt(dex));
//break;
//For each production rule
for(int i=0; Code.length>i;i++){
//If rule applies,
if(Code[i].charAt(0) == wkString.charAt(dex)){
//make substitution for nonterminal creating a new working string
String[] work = wkString.split(NonTerm);
String sub = Code[i].substring(3);
switch (work.length) {
case 0:
//Recursive call to processData with new working string
if(processData(inString, sub))
return true;
break;
case 1:
//Recursive call to processData with new working string
if(processData(inString, work[0] +sub))
return true;
break;
case 2:
//Recursive call to processData with new working string
if(processData(inString, work[0] + sub + work[1]))
return true;
break;
default:
break;
}
}// check non-terminals

}// end for non-terminal
  
}// end if termianl
// // If no nonterminals exist in wkString then return false
// if(NonTerm == "")
// return false;
}// end parse of string
return false;
}//End For end processData       

}

NOTE : PLEASE UPVOTE ITS VERY MUCH IMPORTANT FOR ME A LOT. PLZZZZ......