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.

Improve this question
$\endgroup$
5
  • 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$
    – John L.
    Oct 21, 2018 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$
    – user1233156
    Oct 21, 2018 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, 2018 at 23:28
  • $\begingroup$ @rici yes, that is correct !! It's "or", not "and". $\endgroup$
    – user1233156
    Oct 21, 2018 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$
    – John L.
    Oct 22, 2018 at 2:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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