I think you're on the right track with a PDA! It seems like a good way to approach this problem. I see 2 big issues with this: 1)the naming of your variables, and 2) the high number of magic values. Here are my thoughts.

Naming

In main() for example, the user enters a string. I assume the string is intended to represent a sequence of bases? If so, it should be called something like base_sequence.

Similarly, the argument names in your functions tend to be a single character which conveys no meaning whatsoever to a reader. In the constructor to PDA, you have an argument named l. A single lowercase letter L is a really bad variable name because it looks a lot like a number 1 at first glance. Someone reading the code could easily confuse one for the other, so at least call it lng or lang, or better yet, language. (Or, since it's not actually used ever anywhere, get rid of it!)

The next method of PDA takes a single char named a. Looking at the interface for this class, I have no idea what a represents. The comment says symbol to be read. Why not name it that way? Something like nextSymbol, or nextInput, or better yet, next_base since it represents a base from the base sequence. Also, the name next conveys very little. Next what? How about nextState() or processNextBase()? And the transitionfunction() function has both of those problems as well. Again, b is a base, so name it that way. You don't usually need to put the word function in the name of a function (unless it's returning a function pointer, for example).

And why is your stack called stark?

Magic Values

In transitionfunction(), what does it mean that the top of the stack contains the character $? Or 1 or 2, or any other value? You should either make named constants for them or define an enumerated type for them. That way, someone reading your code will understand the purpose of them.

Simplify

I think your transitionfunction() function could be simplified in a number of ways. I'll break them down in order of easiest to hardest.

First, you don't need any of the top-level elses since once you enter one of them, the function returns. So the structure could be more like this:

if (cur == PDA::FAIL) { return cur; } if (stacktop == '$') { //... internal "if"s } if (stacktop == '1') { // ... internal "if"s } etc. 

Next, it might make sense to break the body of the top-most ifs into separate functions. So something like this:

if (stacktop == '$') { return handleS(b); } if (stacktop == '1') { return handle1(b); } if (stacktop == '2') { return handle2(b); } ... etc. 

Of course, I'd name the handlers something clearer than handleX to make it clear what those states represent.

You can then rearrange the above into a switch statement like this:

switch (stacktop) { case '$': return handleS(b); break; case '1': return handle1(b); break; case '2': return handle2(b); break; ...etc. }; 

You can do the same in the handleX() functions:

switch (b) { case 'a': stark.push('u'); stark.push('1'); return PDA::IN_PROGRESS; break; case 'c': //... code for the 'c' base break; ... etc. } 

But do you notice something? Every case in the handleX() functions will consist of up to 4 operations:

1. optionally pop the stack
2. push a base
3. optionally push a number
4. optionally set the state change to 1

And then they return PDA::IN_PROGRESS. This seems like a potential candidate for a table-driven design. You could define a struct that holds these things. Something like this:

struct StateChange { bool popStack; char base; char number; // use a better name here bool setStateChange; StateChange(bool popIt, char newBase, char newNumber, bool shouldChangeState) : popStack(popIt), base(newBase), number (newNumber), setStateChange(shouldChangeState); }; 

Then you can create std::map of these. Let's look at the $ case:

using StateChangeMap = std::map<char, StateChange>; StateChangeMap dollarStates; dollarStates [ 'a' ] = StateChange(false, 'u', '1', false); dollarStates [ 'c' ] = StateChange(false, 'g', '1', false); // ... etc. for the rest of the '$' states 

Then you can put each of those into another map where the key is the stacktop value that's passed into transitionfunction(). Your transition function now looks something like:

PDA::State PDA::transitionfunction(const char b, PDA::State cur, const char stacktop) { if (cur == PDA::FAIL) { return PDA::FAIL; } StateChange nextState = transitionMap [ stacktop ][ b ]; if (nextState.popStack) { stark.pop(); } stark.push(nextState.base); if (nextState.number != '0') { // Here I'm using '0' to represent not pushing a number stark.push(nextState.number); } if (nextState.setStateChange) { statechange = 1; } return PDA::IN_PROGRESS; } 

Note that you'll either need to use std::map::find() rather than the operator[] that I used if you haven't sanitized the input, or you'll need to sanitize the input so you never get an invalid state value.