New answers tagged

1 vote

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

As the other answers indicate, the language is indeed context-free. Writing a grammar for it is a bit tricky, but we can do it as follows. $N_a(x) = N_b(x)$ First, let's consider the (much) simpler ...
ruakh's user avatar
  • 623
1 vote

Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

Note that the context-free languages are closed under left-quotient as well as intersection with regular languages, as John L. noted. Assume, for contradiction, that $L$ was context-free. Then $$L_1 :=...
Knogger's user avatar
  • 595
2 votes

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

Suppose that instead of a stack, you had a single counter, $x$, that you could either increment or decrement, under the control of a non-deterministic finite-state machine. (Each transition of the ...
D.W.'s user avatar
  • 158k
3 votes

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

The language is context-free. Slightly different: Context free grammar construction $\{ a^mb^n \mid m≤n≤2m \}$. For strings where the symbols $a,b$ may be in any order, you might find inspiration in ...
Hendrik Jan's user avatar
  • 30.4k
3 votes
Accepted

Pumping Lemma Applied to 3 Variables

You seem to misunderstand a bit how the Pumping lemma works. You're not free to choose the value of $p$ or how to divide the string, but need to show that there's no factorization for some $w \in L$ ...
Knogger's user avatar
  • 595
3 votes

How to handle multiple exponents (Pumping-Lemma)

There is a solution to your pumping problem using the classical formulation of the Pumping Lemma, writing $w=xyz$ and considering $|xy| \le p$ and $xy^iz$ for $i\ge 0$. The trick is pumping down... ...
Hendrik Jan's user avatar
  • 30.4k
4 votes
Accepted

How to handle odd word

I have no idea what exactly you're asking, but if you consider $w = a^{2p}$ to be a valid answer for even-sized words, I assume $w = a^{2p+1}$ would be fine for odd words.
orlp's user avatar
  • 12.9k
3 votes
Accepted

How to handle multiple exponents (Pumping-Lemma)

There is actually a more generalized version of the pumping lemma, where you can pump a substring anywhere in the word. The proof is almost the same: in a computation of a word $w$ in a DFA, if there ...
Nathaniel's user avatar
  • 13.8k
0 votes
Accepted

Can we say $|xy^iz| = a^{p+i|y|}b^p$?

What you suggested does not work. As a sanity check, consider pumping down with $i = 0$ -- this should result in a word with a fewer number of a's. If you consider the word $w = a^p b^p$, where $p >...
Bader Abu Radi's user avatar
1 vote

Pumping Lemma Contrapositive, why is this proof wrong?

You're not allowed to assume that $y$ contains both 0s and 1s. Take for example $x = \varepsilon$, $y = 0$ and $z = 0^{\lceil \frac{p}{2} \rceil - 1}1^{\lceil \frac{p}{2} \rceil}$ with $w = xyz$, then ...
Knogger's user avatar
  • 595
1 vote
Accepted

How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the question you've linked, we have $|xy| = |x| + |y| \leq p$ (property b) so $|y| \leq p$ since $|x| \geq 0$. Therefore $$|xy^2z| = |xyz| + |y| = 2^p + |y| \leq 2^p + p < 2^{p + 1}.$$
Knogger's user avatar
  • 595

Top 50 recent answers are included