I've got a language L: $$ \Sigma = \{a,b\} , L = \{a^nb^n | n \ge 0 \} $$
And I'm trying to create a context-free grammar for co-L.
I've created grammar of L:
P = { S -> aSb S -> ab | epsilon
}In co-L, I don't know how to ensure, that there won't be the same number of a,b. Should I create something like this?
P = { S -> aSb S -> a | b | aS | bS
}4 Answers
$\begingroup$Consider this logic: a sentence in the complement of $L$ either should start with $b$ or end in $a$ or if it starts with $a$ and ends with $b$ the substring between the two must not be in $L$ (should be in the complement of $L$). So we can write:
$S\to bA|Aa|aSb$
$A \to aA|bA|\epsilon$
$\endgroup$ 4 $\begingroup$We can break this language into the union of several simpler languages:
L = { $a^i b^j$ | i > j } ∪ { $a^i b^j$ | i < j } ∪ $(a ∪ b)^∗b(a ∪ b)^∗a(a ∪ b)^∗$.
That is, all strings of a’s followed by b’s in which the number of a’s and b’s differ, unioned with all strings not of the form $ a^ib^j$.
First, we can achieve the union of the CFGs for the three languages:
S → $S_1|S_2|S_3$
Now, the set of strings { $a^ib^j$ | i > j } is generated by a simple CFG:
$S_1 → aS_1b|aS_1|a$
Similarly for { $a^ib^j$ | i < j }:
$S_2 → aS_2b|S_2b|b$
Finally, $(a ∪ b)^∗b(a ∪ b)^∗a(a ∪ b)^∗$ is easily generated as follows:
S3 → XbXaX
X → aX|bX|ϵ
Source:
$\endgroup$ 1 $\begingroup$The strings not of form $a^nb^n$ come in several groups.
A string starting with $b$ can be gotten via $S \to bS_1$, then $S_1 \to aS_1|bS_1|\varepsilon $
A string may have a positive number of $a$, then a positive number of $b$, then a positive number of $a$ and then anything. This one takes more steps: $S\to aS_2$, then $S_2 \to aS_2|bS_3$, then $S_3 \to bS_3|aS_4$, then $S_4 \to aS_4|bS_4|\varepsilon.$
Remaining strings in the complement have $a$'s followed by $b$'s but either more $a$ on the left or more $b$ on the right. For more $a$ on the left, use $S \to aS_5,$ then $S_5 \to aS_5|aS_5b|\varepsilon$ Finally for more $b$ on the right use $S \to S_6b,$ and then $S_6 \to S_6b|aS_6b|\varepsilon.$
I'm not an expert on this topic, but the above looks intuitively to me like it covers all the strings in the complement of $a^nb^n$ while not letting any of the latter be produced.
$\endgroup$ $\begingroup$a^n b^n means equal number of a following equal number of b
Grammar g={N,T,P,S}
N- Non Terminals-{A}
T- Terminals-{a,b,epsilon}
p- Production
S->A
A->aAb
A->Epsilon(^)
S- Start Symbol-{S}
Hope this answer is correct ANWAR MULLA (AGCE)
$\endgroup$ 1
