Consider the LanguageL of oddlength palindromes over alphabet (a,b,c) of the form (wcw: 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). 1. Writea C++program that will allow the user to input a string (consisting of a's, b'sandc's), checks if the string is valid or invalid string for the language based on the given transition rules of the 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 ofstack data structure in C++. You are not expected to implement stack data structure. Note that the PDA is a deterministic PDA soit will makethings a little simpler Some example valid strings are c, aaaacaaaa, abcba, babacabab. Example invalid strings areaaaacbbbb, abcab, abab, aaaaaa. ? / push(a), b,? / push(b) a,a/pop, b,b/pop C