0
$\begingroup$

Here, $Σ=\{a,b\}$ The number of $a$ can be $1, 4, 7, 10.....$, also $a$ can be placed anywhere.

Find Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$

How can I proceed in this problem?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

You haven't indicated your alphabet, so let me assume that it is $\{a,b\}$, though this makes little difference.

In order to create a regular expression for your language, you can use the following two steps:

  1. Write a regular expression for the language of all words $w$ over the alphabet $\{a\}$ such that $n_a(w) \equiv 1 \pmod{3}$.
  2. Add back the $b$s to the regular expression. One way to do it is to replace each $a$ by $ab^*$, and to add an additional $b^*$ as a prefix.
$\endgroup$
0

Your Answer

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

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