patternMinor
Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
Viewed 0 times
midacceptlanguagepdaconstructinggeq0
Problem
I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
Solution
Your language is equivalent to the language $a^ib^ib^{2k}c^k$, and since concatenation is associative, this is equivalent to $(a^ib^i)(b^{2k}c^k)$.
A PDA for the first of these parts pushes an $a$ for each $a$ it sees and pops an $a$ when it sees a $b$. If the topmost stack symbol after this is $Z_0$, transition to the second PDA, which pushes a $b$ for every two $b$s it sees and then pops a $b$ for every $c$ it sees, accepting if, after this, you end up with no input and $Z_0$ as the topmost symbol.
A PDA for the first of these parts pushes an $a$ for each $a$ it sees and pops an $a$ when it sees a $b$. If the topmost stack symbol after this is $Z_0$, transition to the second PDA, which pushes a $b$ for every two $b$s it sees and then pops a $b$ for every $c$ it sees, accepting if, after this, you end up with no input and $Z_0$ as the topmost symbol.
Context
StackExchange Computer Science Q#10319, answer score: 7
Revisions (0)
No revisions yet.