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

Decide if L is regular or not and argue it. Trying to use Pumping Lemma

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
regulartryingarguepumpingdecidelemmaandusenot

Problem

Part (a): Let $L = \{x \in \{0,1\}^* \mid \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$.

So I want to use the pumping lemma. But I'm having a hard time choosing a string so that I can show that it is not regular.

I've been thinking about how I could use something like the string, s, = $0^{3p}1^p$. But I do not see how you use that fact (I would like to show that xyyz would equal $0^{4p}1^p$). This route seems unfruitful. So any help would be nice.

Part (b): Let $L = \{x \in \{0,1\}^* \mid \exists k \in \mathbb{N}, \#0(x) + \#1(x) = 2k\}$.

Again stuck on this problem. My original approach was to leverage the fact that the parity is the same on the 0s and 1s (if one is even, then so does the other and vice versa. Same for odd parity.)

Again, this does not seem to be working.

Solution

(a): Recall that regular languages are closed under complement, i.e if $L$ is regular, so is $L'$. ($F_{L'} = Q_L- F_L$)

Assume that $L$ is regular.
This follows: if $L = \{x \in \{0,1\}^ \mid |x|_0 \neq 4.|x|_1 \}$ is regular, then so is $L' = \{x \in \{0,1\}^ \mid |x|_0 = 4.|x|_1\} $

Now you should show that $L'$ is not regular. And that gives you a contradiction.

(b) You can construct the following DFA for this.

Context

StackExchange Computer Science Q#14180, answer score: 5

Revisions (0)

No revisions yet.