-1
$\begingroup$

I'm asked to categorize the language $L=${$a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}$}, therefor I need to distinguish if it's regular, context free, or non context free (in $P$)

We know CFLs are closed under union, and I belive $L_1=${$a^nb^m : n<7m$} can be represented by the CFG $S\rightarrow Ab | aAb | aaAb | ... |aaaaaaAb \\\ A\rightarrow Ab | aAb | aaAb | ... |aaaaaaAb | \epsilon $

(I'm not completely sure in the correctness of this CFG, but I belive it shows the idea of $L_1$)

However I am unsure on how to represent $L_2=${$a^nb^m : n>7m$} in CFG form, it seems like the construction rules of $L_2$ would be 8 appearences of $a$ per $b$, but theres no upper limit on the number of appearences of $a$, which got me in a freeze in progressing with this.

this prevents me from claiming that $L_1\cup L_2=L$ is CFL under closure properties

A little edit: I've created this PA:PA

which I believe accepts $L_2$, the basic logic behind it is : read all $a$'s, for each $b$ you see take out 7 appearances of $a$, if you have any $a$'s left in your stack, you can accept the word.

Again, I'm unsure in the correctness of this PA, yet I cant come up with a word in $L_2$ that wont be accepted by this PA.

$\endgroup$
1
  • $\begingroup$ There is a "high-level" closure property that is applicable here: If $L\subseteq a^*b^*$ is context-free, then its relative complement $a^*b^* \setminus L$ is context-free. cs.stackexchange.com/q/11110/4287 This will not help in constructing an explicit grammar, though. $\endgroup$ Commented Feb 26 at 19:48

2 Answers 2

2
$\begingroup$

An easy way prove the language context free is to use the closure properties of context-free languages.

Note that the following grammar with start variable $S$ generates $L' = \{a^nb^m : n = 7m\}$

$$S \to a^7Sb | \varepsilon.$$

Therefore

$$L_1 = a^+L' = \{a^nb^m : n > 7m\}$$

and

$$L_2 = a^+ \setminus L' = \{a^nb^m : n < 7m\}$$ must be context-free, since the context-free languages are closed under concatenation $\circ$ and (left) quotient $\setminus$ with regular languages. Thus $L = L_1 \cup L_2$ must be context-free as well.


One way to prove that $L$ is non-regular is to show that the language has an infinite number of unique quotients. We have

$$a^k \setminus L = \{a^{n - k}b^m : n \geq k \text{ and } n \neq 7m\}.$$

But since for all $k_1 \neq k_2$ follows that $b^{k_1} \notin a^{7k_1} \setminus L$ and $b^{k_1} \in a^{7k_2} \setminus L$, it follows that for arbitrary $k_1, k_2$

$$a^{7k_1} \setminus L = a^{7k_2} \setminus L \iff k_1 = k_2.$$

So $L$ must have an infinite number of quotients and can't be regular.

$\endgroup$
6
  • $\begingroup$ What does the $a^+$ notation stand for? $\endgroup$
    – Aishgadol
    Commented Feb 26 at 15:02
  • 1
    $\begingroup$ Thats $a^+ = \{a\}^+ = \{a, a^2, a^3 ...\}$, basically $a^*$ without $\varepsilon$. $\endgroup$
    – Knogger
    Commented Feb 26 at 15:06
  • $\begingroup$ I see how $L_1=a^+\circ L'={a^nb^m : n>7m}$, however I cant see how $L_2$ is created, wont $a^+-L'$ just be $a^+$ since $a^+ \cap L' = \emptyset$? $\endgroup$
    – Aishgadol
    Commented Feb 26 at 16:53
  • $\begingroup$ Sorry, that is a bit ambiguous. $a^+ \setminus L'$ isn't meant to be the difference but the (left) quotient. The context-free languages are closed under quotient with regular languages, I'll edit the question later to make this clearer. $\endgroup$
    – Knogger
    Commented Feb 26 at 17:03
  • $\begingroup$ *answer, not question 😅 $\endgroup$
    – Knogger
    Commented Feb 26 at 20:05
0
$\begingroup$

You add either 0 to 6 a's on the left and one or more b's on the right, or you add one or more a's on the left. Then you add 7 a's on the left and one b on the right zero or more times.

$\endgroup$
2
  • $\begingroup$ I dont seem to understand this, could you perhaps elaborate? $\endgroup$
    – Aishgadol
    Commented Feb 26 at 17:17
  • $\begingroup$ The first makes n<7m with n <= 6, the second makes n > 7m with m = 0, then you add more characters with n = 7m. $\endgroup$
    – gnasher729
    Commented Feb 27 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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