<p>I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way?</p>
<p><strong>Problem:</strong>
Given <span class="math-container">$n \in \mathbb{N}^+$</span>. Consider the language <span class="math-container">$L := \{ wa^{w_2} | w \in \{0, 1\}^n\}$</span>. Construct a deterministic PDA for <span class="math-container">$L$</span> using <span class="math-container">$O(n)$</span> stack symbols and states. Additionally, the stack height should be bounded by <span class="math-container">$O(n)$</span>.
An example would be <span class="math-container">$1100a^{12} \in L$</span></p>
<p><strong>Solution Sketch:</strong>
Let <span class="math-container">$(Q, \Sigma, \Gamma, q_n, Z_0, \delta)$</span> be the PDA, where:</p>
<ul>
<li><span class="math-container">$Q := \{q_0, \dots , q_n\}$</span></li>
<li><span class="math-container">$\Sigma := \{0, 1, a\}$</span></li>
<li><span class="math-container">$\Gamma := \{Z_0, A_1, \dots , A_n\}$</span></li>
</ul>
<p>Define the transition function <span class="math-container">$\delta$</span> as follows:</p>
<ul>
<li><span class="math-container">$\delta(q_i, 0, X) := \{(q_{i−1}, X)\}$</span>, for <span class="math-container">$i \in \{1, \dots , n\}, X \in \Gamma$</span></li>
<li><span class="math-container">$\delta(qi, 1, X) := \{(q_{i−1}, A_i X)\}$</span>, for <span class="math-container">$i \in \{1, \dots , n\}, X \in \Gamma$</span></li>
<li><span class="math-container">$\delta(q_0, \epsilon, A_i) := \{(q_0, A_{i−1}A_{i−1})\}$</span>, for <span class="math-container">$i ∈ {2, . . . , n}$</span></li>
<li><span class="math-container">$\delta(q_0, a, A_1) := {(q_0, \epsilon)}$</span></li>
<li><span class="math-container">$δ(q_0, \epsilon, Z_0) := {(q_0, \epsilon)}$</span></li>
</ul>
<p><strong>Idea:</strong>
For each power of two <span class="math-container">$2^i$</span>, introduce a stack symbol. If we encounter the stack symbol for <span class="math-container">$2^0 = 1$</span>, we read an &quot;a&quot;. Otherwise, we break down the stack symbol for <span class="math-container">$2^{i+1}$</span> into two stack symbols for <span class="math-container">$2^i$</span>.</p>

CC BY-SA 4.0
2023-07-18T11:24:23.880Z
What does a^(w)2 mean?
Martin Berger
CC BY-SA 4.0
2023-07-18T18:23:40.193Z
@MartinBerger like for example 1100a^12 1100 is the binary representation followed by a and then power of the number
Hanshika
CC BY-SA 4.0
2023-07-18T20:36:33.760Z
In your example, is $a$ repeated 12 times, i.e. the word is $1100aaaaaaaaaaaa$ ?
Martin Berger
<automata-theory>
Construction of a PDA for the binary and decimal representation of a number
Hanshika
# Construction of a PDA for the binary and decimal representation of a number

(Asked by: username_0 on 2023-07-17)

I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way?

**Problem:**
Given $n \in \mathbb{N}^+$. Consider the language $L := \{ wa^{w\_2} | w \in \{0, 1\}^n\}$. Construct a deterministic PDA for $L$ using $O(n)$ stack symbols and states. Additionally, the stack height should be bounded by $O(n)$.
An example would be $1100a^{12} \in L$

**Solution Sketch:**
Let $(Q, \Sigma, \Gamma, q\_n, Z\_0, \delta)$ be the PDA, where:

* $Q := \{q\_0, \dots , q\_n\}$
* $\Sigma := \{0, 1, a\}$
* $\Gamma := \{Z\_0, A\_1, \dots , A\_n\}$

Define the transition function $\delta$ as follows:

* $\delta(q\_i, 0, X) := \{(q\_{i−1}, X)\}$, for $i \in \{1, \dots , n\}, X \in \Gamma$
* $\delta(qi, 1, X) := \{(q\_{i−1}, A\_i X)\}$, for $i \in \{1, \dots , n\}, X \in \Gamma$
* $\delta(q\_0, \epsilon, A\_i) := \{(q\_0, A\_{i−1}A\_{i−1})\}$, for $i ∈ {2, . . . , n}$
* $\delta(q\_0, a, A\_1) := {(q\_0, \epsilon)}$
* $δ(q\_0, \epsilon, Z\_0) := {(q\_0, \epsilon)}$

**Idea:**
For each power of two $2^i$, introduce a stack symbol. If we encounter the stack symbol for $2^0 = 1$, we read an "a". Otherwise, we break down the stack symbol for $2^{i+1}$ into two stack symbols for $2^i$.

**Tags:** automata-theory
> **Comments:**
> **username_1**: What does a^(w)2 mean?  
> **username_0**: @MartinBerger like for example 1100a^12 1100 is the binary representation followed by a and then power of the number  
> **username_1**: In your example, is $a$ repeated 12 times, i.e. the word is $1100aaaaaaaaaaaa$ ?  

---

## 0 answers

