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

Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

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

Context

StackExchange Computer Science Q#10319, answer score: 7

Revisions (0)

No revisions yet.