Cfrgtkky

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

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 $sin Sigma^*$ can be written as $s=usigma$ where $uin Sigma^*$ is a subword and $sigmainSigma$ 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.