$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$
$\bullet $ #$_b$ denotes the number of $b$'s in $w$
$\bullet $ #$_c$ denotes the number of $c$'s in $w$
I have some trouble designing a CFG for the language above. How can I do this?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ I do not believe the language $L$ to be context-free. If it was context-free then, by the pumping lemma for context-free languages there exists a number $p$ such that any string $s \in L$ of length at least $p$ can be split into $s = u v w x y$ satisfying conditions $1$ to $3$ of the pumping lemma. Consider the string $s = a^p b^p c^p \in L$ - no split of $s$ can satisfy all conditions of the pumping lemma, therefore $L$ is not context-free. $\endgroup$– AcIdApr 28, 2019 at 11:30
-
1$\begingroup$ @AcId's comment is true if you mean (#a = #b and #a = #c). But there is a CFG if you mean (#a = #b + #c). Can you clarify what "number of a's is equal to number of b's and number of c's" means? $\endgroup$– frabalaApr 28, 2019 at 11:38
-
$\begingroup$ @frabala You are right; in the latter case the language would be context-free. $\endgroup$– AcIdApr 28, 2019 at 11:52
-
$\begingroup$ @Acld For instance aabc, aacc or ab $\endgroup$– Fatih CanbekliApr 28, 2019 at 13:37
-
$\begingroup$ The rules of your CFG should ensure that every time an $a$ is produced in the lead part of the string, then either a $b$ or a $c$ should be produced in the trailing part of the string. $\endgroup$– AcIdApr 28, 2019 at 16:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I believe the following CFG meets the requirements
$$ S \to aSB \mid \varepsilon\\ B \to b \mid c $$
$\begingroup$
$\endgroup$
I believe, the answer of @Acid is correct.
Also, It is sometimes hard to come up with the productions rules directly by looking at the language.
An easier (a bit longer) approach can be, making a Push Down Automata (PDA) accepting the given language and converting the transitions of PDA into production rules.
For this language, it can be observed that, we can just push some stack symbol let's say '#' into the stack on seeing 'a' as the input symbol and pop from the stack on seeing 'b' or 'c'. Also make sure that, 'a' never comes after we see at least one 'b' or 'c'.
Once the PDA is done, this is a very informative video on converting to PDA to CFG.
Let me know in the comments, if you need any clarification in the conversion.
