0
$\begingroup$

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?

$\endgroup$
2
  • $\begingroup$ Your language is context-free. Someone already asked this question on this site, and got a full answer (including a grammar). $\endgroup$ – Yuval Filmus Dec 3 '20 at 9:18
  • $\begingroup$ Here is my answer to a remarkably similar question. $\endgroup$ – Yuval Filmus Dec 3 '20 at 11:42
0
$\begingroup$

What's the smallest possible j, and which i goes with it (to allow j < i < 2j). So that's the minimum number of a's and b'. Beyond that, you need one or two a's for every additional b.

That should be enough to find a grammar.

$\endgroup$
0
$\begingroup$

To show a language is context free we can create a context free grammar for it then show that it generates all strings in the language.

Consider the following grammar $G$.

S -> aaaRbb
R -> aRb | aaRb | eps

We must prove that $L(G) = L$.

Proof: The variable $S$ in the grammar starts off with the smallest string in $L$. This string is $aaabb$ with $j=2$ and $i=3$ (since $0 < j = 2 < i = 3 < 2j = 4$).

The repetition happens within the variable $R$. Consider the string $s = a^ib^j \in L$. We want to see whether the string $s' = a^{i+1}b^{j+1}$ is in $L$. The first three conditions are trivial ($0 < j+1 < i+1$). The last condition is quick to check: \begin{align} i+1 &< 2(j+1) \\ i+1 &< 2j+2 \\ i &< 2j+1 \\ \end{align} So $s' \in L$. We can show $s' = a^{i+2}b^{j+1} \in L$ similarly.

The rules R -> aaaRb, R -> aR, and R -> Rb cannot be in our grammar as it can generate strings that are not in the language. As an example, the strings aaaaaabb, aaaabb, and aaabbb can be generated if we add the above rules which are not in $L$.

Thus, $G$ is complete. Hence, $L(G) = L$.

As for creating a pushdown automata, there are many guides on how to construct a PDA from CFG. The following links will be useful (just from a quick google search).

  1. Convert CFG to CNF
  2. Convert CFG to GNF
  3. Construct PDA from CFG
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.