HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Constructing deterministic PDA for not regular language

Submitted by: @import:stackexchange-cs··
0
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.

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.