The second topic today is about PSA, a updated version of FSA, that we are allowed to use a stack. This is the perfect case that we can use this stacked automate to solve some problems like Matching Parentheses or like the one we left after lecture, same number ones and zeros. I didn't get a chance to think this question deeply before I wrote this slog. I think I have some sort of clue that when we see a 0, we push 0 to the stack, when we see a 1, we pop a 0.
we need to have a start states and two states that paralleled to each other that accepting 1:/epsilon X and 0:/epsilon X respectively. Furthermore, we need to have another states that connecting with the two states mentioned above, realize that I should label them as S1 and S0, then they connected to the states S3 say... to be continued...
No comments:
Post a Comment