edited by
8,955 views
21 votes
21 votes

Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$. Which of the following is true?

  1. $L = \left\{x \mid x \text{ has an equal number of } a\text{'s and }b\text{'s}\right \}$ is regular
  2. $L = \left\{a^nb^n \mid n \geq 1\right \}$ is regular
  3. $L = \left\{x \mid x \text{ has more number of }a\text{'s than }b\text{'s}\right \}$ is regular
  4. $L = \left\{a^mb^n \mid m \geq 1, n \geq 1 \right \}$ is regular
edited by

2 Answers

Best answer
20 votes
20 votes

Correct Option: D

Since $n$ and $m$ are independent finite memory suffices.

Options (a) and (b) are the same. They and option (c) require keeping track of the counts of $a’s$ which cannot be done using a finite automata but can be done using a DPDA and hence are not regular but DCFL.

edited by
2 votes
2 votes
  • in option a,b,c  there is one compatision between a and b . which is done bt pda. so it is CFL but not regular.

 

  • in option d we can write a regulag expression (aa*bb*) . so it is regular
Answer:

Related questions

14 votes
14 votes
4 answers
1
17 votes
17 votes
2 answers
3
Kathleen asked Oct 9, 2014
5,541 views
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the...