# Context-Free Grammar from this language

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.

• 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$. Oct 21, 2018 at 22:13
• 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) Oct 21, 2018 at 22:27
• @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).
– rici
Oct 21, 2018 at 23:28
• @rici yes, that is correct !! It's "or", not "and". Oct 21, 2018 at 23:32
• @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 Oct 22, 2018 at 2:45

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.