Test by Bikram | Mock GATE | Test 4 | Question: 53

Question

Which of the following languages over the alphabet set $\{ a, b \}$ is described by the regular expression

$a^\ast b$(aa)$^\ast b$ ?

• A. The set of all strings containing exactly two $b’s$.
• B. The set of all strings having even number of $a's$ between exactly two $b’s$ and ending with $‘b’$.
• C. The set of all strings ending with $‘b’$.
• D. The set of all strings having sub sequence $bb$.

Comments

how it produce even no of a ????

it will genrate like string abaab which is not even

---

@Arjun sir. Someone edited the question to: a*b(aa)a*b

---

fixed now. Thanks.

---

That was quick!!

Sir it's hard to get to you. So can you please answer my one doubt. _/\_

It's not related to this question, but to this one: https://gateoverflow.in/129723/go-full-mock-4-39

Sir, how can we encode the flag bits. More than one flag can be high in a single clock. If we encode it we won't be able to represent this information. 

Suppose we have 4 flags. Then we need MINIMUM 4 bits to represent them. Any $2^{4}$ combination of flags being on and off is possible. So how can we encode it to $\log 4$ bits?

Answer 1

$a$*$b$$\left ( aa \right )$*$b$  

Best statement that says about this regular expression is the set of all strings having an even number of a's between exactly two b’s and ending with ‘b’.

option A: The set of all strings containing exactly two $b’s$.(False)

for eg: $\left \{ abb, abbbb, ababab..... \right \}$ these all strings are not accepted by given a regular expression

option C:  The set of all strings ending with ‘$b$’. (False)

for eg: $\left \{ abb, abbbb, ababab..... \right \}$ these all strings are not accepted by given regular expression

option D: The set of all strings having sub sequence $bb$.(False)

for Eg: $\left \{ abab, abbaaaa, aaaabaaaab..... \right \}$ these all strings having subsequence bb but not taken as granted by given regular expression...

option $B$ is answer...

Comments

"abb" is not accepted! Why? Can't we generate a from a* and bb from remaining two b's ?