0
$\begingroup$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given.

The first question : Is this language regular?
The second question : If $L$ is regular, How can we write a regular expression for it?
The third question : If i change $L$ to $L'=\{w \in \{a,b,c\}^*:n_a(w)=3 \land n_b(w)=4\}$ , Answer the first and the second question about it.

Note : Generally i know how to write regular expression for a language. But in this case, i can't even draw a DFA for L so that i can convert it to regular expression.

$\endgroup$
0
$\begingroup$

$L$ is finite, so it’s certainly regular: it consists of all $7$-letter words over $\{a,b\}$ that contain exactly $3$ $a$s and $4$ $b$s. There are $\binom73=35$ such words. One regular expression for the language simply lists all $35$ of these words in a long disjunction:

$$aaabbbb+aababbb+aabbabbb+\ldots+bbbbaaa\;.$$

$L'$ is still regular: a word is in $L'$ if and only if what’s left after you delete all of the $c$s in it (if any) is one of the $35$ words in $L$. Equivalently, $L'$ consists of all of the words that you can get by starting with a word in $L$ and adding zero or more $c$s anywhere in that word. That approach gives you one (admittedly ugly) regular expression for $L'$.

$\endgroup$
  • $\begingroup$ @Arman: You’re welcome. $\endgroup$ – Brian M. Scott Apr 14 '16 at 8:51

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.