0
$\begingroup$

I'm having difficulties with an exercise in a theoretical CS class. The problem is:

let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast one "a".

What is the CFG that creates $L_{2}$?

I'm struggling since 2h... I've found out that for example "abba" is not in the language, but to write it formally is quite difficult. Help would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Welcome come to Computer Science! The condition is not clear enough for me. Suppose the alphabet only has $a$ and $b$. What would be the last symbol in a word in $L_2$? If it is $a$, no $b$ follows it. If its $b$, no $a$ follows it. So there is no non-empty word in $L_2$. $\endgroup$ – Apass.Jack Oct 21 '18 at 22:13
  • $\begingroup$ Thanks for the reply. Actually $L_{2} = \{\omega \in \{a,b\}^*...$ and then the the condition like I wrote in the beginning. It also states that "b", "abbbbbabb", "aaaabaaaba" also "$\epsilon$" are in the language. ( the term is {a,b}^*, but I suck at formatting...sry first time) $\endgroup$ – Neon Xd Oct 21 '18 at 22:27
  • 1
    $\begingroup$ @apass: I assume that by "or" they mean "or", rather than "and" (which is how you appear to have interpreted it). So every non-empty word in the language satisfies one of the two predicates (since, as you say, it's impossible for a non-empty word to satisfy both). $\endgroup$ – rici Oct 21 '18 at 23:28
  • $\begingroup$ @rici yes, that is correct !! It's "or", not "and". $\endgroup$ – Neon Xd Oct 21 '18 at 23:32
  • 1
    $\begingroup$ @rici, thanks. My bad (lunch saturation). Consider language $L_3$, in each word of which every $a$ is followed by at least two $b$'s. Can you construct CFG for $L_3$? Consider the language $L_4$, in each word of which every $b$ is followed by at least one $a$. Can you construct CFG for L_4? In fact, $L_3$ and $L_4$ are regular languages $\endgroup$ – Apass.Jack Oct 22 '18 at 2:45
0
$\begingroup$

As Aspass.Jack wrote in the comments, let's first define $L_3$ to be the language where each $a$ is followed by at least 2 $b$'s, and $L_4$ to be the language where each $b$ is followed by at least one $a$.

Now, if let's say you can define CFGs for $L_3$ and $L_4$ with start symbols $S_3$ and $S_4$. Then, we simply need to define a grammer with the transition: $$S \rightarrow S_3|S_4$$ together with all the transitions from the other 2 CFGs. Hopefully this simplifies your problem.

$\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.