1. Consider the LanguageL of oddlength palindromes over alphabet (a,b,c) of the form (wewR: w e (a,b)*, wR is w in reversed form.). A final state acceptance PDA is given below that recognizes this language (? Simply means any non empty symbol). Writea C++program that will allow the user to input a string (consisting of a's, b's andc's), checks if the stringis valid or invalid string for the language based on the given transition rules ofthe PDA. The program should also display the contents of the stack after reading every letter in the input string. You can use the pre-defined implementation of stack data structure in C++.You are not expected to implement stack data structure. Note that the PDA is a deterministic PDA so it will makethings a little simpler Some example valid strings are c. aaaacaaaa, abcba, babacabab. Example invalid strings areaaaacbbbb, abcab, abab, aaaaaa /push(a), b,7/ push(b) a,a/pop, b,b/pop