Let $L_4$ be the language over alphabet $\{0, 1\}$ defined by $L_3 = \{x : \#_1(x) = 2 \cdot \#_{10}(x)\}$ design for a PDA that accepts $L_4$

Question

Let $L_4$ be the language over alphabet $\{0, 1\}$ defined by $L_4 = \{x : \#_1(x) = 2 \cdot \#_{10}(x)\}$

Here is a design for a PDA that accepts $L_4$. See diagram below, where we use e to donote $\epsilon$

-For a string $x$, we use k to stand for the quantity $\#_1(x) - 2 \cdot\#_{10}(x)$

-If $k = 0$, then the stack should be empty

-If $k \neq 0$, then the stack should have a $Y$ at the bottom and $|k| - 1$ Xs on top.

-$q_0, q_1$ are for $x$ where $k = 0$. $q_0$ is for $x$ that does not end with 1. $q_1$ is for $x$ that ends with $1.$

-$q_2, q_3, q_4$ are for $x$ where $k > 0$. $q_2$ is for $x$ that ends with $1.$ $q_3$ is an extra state to sllow for popping 2 items off the stack. $q_4$ is for x that ends with $0$.

$q_5, q_6, q_7$ are for x where $k < 0$. $q_5$ is for x that ends with $0$. $q_6$ is an extra state to allow for pushing 2 items on the stack. $q_7$ is for x that ends with $1$.

Complete the PDA by adding appropiate transitions. To help you get started initial state is indicated some transitions are given, and accepting states are indicated by double parentheses.

My attempt:

Not sure how to really go about this. I tried to satisfy very easy cases like the empty string is already accepted. 101 is accepted. But keep ending up stuck because I need to have k-1 x's

Answer 1

From the transitions and information given, we can deduce the following:

• A string only ends in $q_0$ if it is in $L_4$ and ends in a $0$.
• A string only ends in $q_2$ if $k>0$ and it ends in $1$.
• No string ends in $q_3$.
• A string only ends in $q_4$ if $k>0$ and it ends in $0$.
• A string only ends in $q_1$ if it is in $L_4$ and ends in a $1$.
• A string only ends in $q_5$ if $k<0$ and it ends in $0$.
• No string ends in $q_6$.
• A string only ends in $q_7$ if $k<0$ and it ends in $1$.
• Every transition to $q_0$, $q_3$, $q_4$, $q_5$, or $q_6$ transitions on a $0$ or $\epsilon$.
• Every transition to $q_1$, $q_2$, or $q_7$ transitions on a $1$ or $\epsilon$.

Given any string in $\Sigma^*$ (even ones not in $L_4$) we can figure out which state it should end in based off of the above information. Also, if a word $s\in \Sigma^*$ can be written as $s=u\sigma$ where $u\in \Sigma^*$ is a subword and $\sigma\in\Sigma$ is a character, then if $u$ ends in state $q_i$ and $s$ ends in $q_j$, then there must be a transition from $q_i$ to $q_j$ on $\sigma$. From this information we can begin to fill in transitions by testing small strings and their substrings. Here is my solution.

Let me know if you need clarification.