Question

1. Consider the language defined as such:

L = { w$w’ : w is a string of numbers 0-9 and can be of length ≥ 0, and w’ is the reverse string of w}

Write a recursive grammar that defines all strings in the language.

2. Using the language above, write the Java code (using recursion) that will recognize if a string is part of the language or not.

Answer 1

(a)Consider the given Language

L = { w$w’ : w is a string of numbers 0-9 and can be of length ≥ 0, and w’ is the reverse string of w}

L={$,0$0,1$1,2$2,01$10,00$00,.....}

The recursive grammar that generate L is G=(V, T, P, S) which are defined as :

V={S}

T={0,1,2,3,4,5,6,7,8,9}

S-is the start Symbol

P={S→0S0/1S1/2S2/3S3/4S4/5S5/6S6/7S7/8S8/9S9/$}

i.e We recursively generate numbers(0-9) in such a way that we can each number start and end with the same digit until we place a $ at the center of the string.

(b)Using the language above, write the Java code (using recursion) that will recognize if a string is part of the language or not.

1.CODE SCREENSHOT :

2.OUTPUT :

3.CODE :

import java.util.Scanner;
class StringRecognizer
{
    
    public static boolean isValid(String s)
    {   // if length is 1 and the input is '$' then we accept
                if(s.length() == 1 &&s.charAt(0)=='$')
            return true; 
                // if length is 1 and the input is Not '$' then we reject
                // if length is 2 then we rejct since L={$,0$0,1$1,...}
                // The string lenght must be odd
                if(s.length() == 1 &&s.charAt(0)!='$'||s.length() == 2)
            return false; 
                /*
                *If we read digits at both end of the input ,then we compare 
                *and check weither the two characters are equal,if equal then
                *we search the remaining substring 
                */
        if(Character.isDigit(s.charAt(0))&&Character.isDigit(s.charAt(s.length()-1)))
                if(s.charAt(0) == s.charAt(s.length()-1))
               return isValid(s.substring(1, s.length()-1));
                //if the input is non  numeric then we return false 
        return false;
    }

    public static void main(String[]args)
    {
        //For capturing user input
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the String for check:");
        String string = scanner.nextLine();
        /* If function returns true then the string is
         * in the language else not
         */
        if(isValid(string))
            System.out.println(string + " is in the given Language");
        else
            System.out.println(string + " is not in the given Language");
    }
}