Use stacks to evaluate if a given string is in a regular language L. The purpose of using a stack is to take advantage of its LIFO nature, therefore algorithms which merely use the stack for storage and determine inclusion of the string in the language by

the use of counting the input string in any manner are not allowed. For example, you may not push letters onto stacks then get the size of the stack in order to determine membership in the language.

Here is an example algorithm that meets the requirements:

Let L1= { w: w contains equal numbers of A's and B's (in any order) and no other characters}

Algorithm:

Input: String W

Create an empty stack S

While String W has characters

read a character c

if S is empty

push c on S

if S.peek is equal to c

push c on S

else

pop S

end while

if S is empty

return true

else

return false

Here are the language you must evaluate:

L2 = { w: w is of the form AnBn, for some n >0 }

(for reference AAABBB = A3B3. This string is in the language with n=3}

L3 = { w: w is of the form (AnBn)p, for some n, p >0 }

L4 = { w: w is of the form (AnBm)p, for some m,n,p >0 }

w = AAABBB

AB

?

( the empty string)

ABABABA

ABAB

BBAA

BBBAA

AAB

AABB

ABCBA

ABBBA

ABBA

ABAABBAAABBB

AA

AABBBAABBB

Test each string given as well as additional strings you make up yourself against each of the four

languages

Write a commentary where you discuss your data structures and their implementation and why they make sense. E.g. why is stack a reasonable choice to solve this problem? What implementation of a stack did you choose? Why? Include the computational complexity of the operations in your code.

Note: You are expected to write the stack code yourself and not use the library stack class. Be sure to include the code for your stack as part of the source code you submit.

DO NOT COPY ANSWER FROM PREVIOUS WRONG ATTEMPTS!!!!

////////////// Using C++ ////////////////////////////