patternMinor
Constructing deterministic PDA for not regular language
Viewed 0 times
regularlanguagepdaconstructingfordeterministicnot
Problem
Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many c’s that can be in front, behind or among the a’s and b’s.
Some words in L are: abc ccacaabcccbccbc
I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts L?
Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas?
Sorry for the horrible drawing in advance.
Some words in L are: abc ccacaabcccbccbc
I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts L?
Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas?
Sorry for the horrible drawing in advance.
Solution
Recipe in shorthand. Ignore $c$'s. Use a bottom fo stack symbol $Z$ that stays there. Keep the surplus of $a$'s on the stack. So $ZAAA$ (top of stack right) means three $a$'s more than $b$'s. If we read another $a$ push $A$, if we read another $b$ pop an $A$ (and move to another state to indicate we have now seen $b$).
Context
StackExchange Computer Science Q#6239, answer score: 2
Revisions (0)
No revisions yet.