Is (a ^ p) (b ^ q) a regular language

Question

I read somewhere that {(a ^ p) (b ^ q): p, Q belongs to N} - a regular language. However, I do not think this is correct. This can be proved using the pumping lemma. I just want to check the correctness of my decision.

Let y be ab. Thus, x (y ^ n) z does not belong to L, since there will be some b to a for n> = 1. However, the expression does not allow this. So (a ^ p) (b ^ q) is not RL

Answer 1

I recently applied the pumping lemma, but ^p b ^{q is} definitely a common language. It’s even trivial to write a regular expression for it! a * b *

The similar form a ^p b ^{p is} not regular, because when you start consuming b-characters, you need to remember how many characters you consumed, and the state machine cannot "remember" an arbitrary number. This is not a problem in your case!

Answer 2

Pumping Lemma says: If A is regular =>, then there exists a number p (pumping length), where s is any string in L such that | s | > = p, then s can be divided into three parts s = xyz satisfying the following condition:

• xy ⁱ z is in L for each i> = 0
• | y | > = 0
• p> = | xy |

The correct way to show that a certain language L is not regular is to consider L regular and try to achieve a contradiction.

If you try to assume that your language is not regular, you should first look for a string type that represents the unevenness of the language. Let's try with ^p b ⁿ for n> = 0.

We can make some assumption on this line: since | xy | <= p, we know that y consists only of a. At this point, you can pump it as many times as you want, but xy ⁱ z is a member of your language for every i> = 0.

Similarly, you will not achieve a contradiction if you choose ⁿ b ^p for n> = 0.

L = {a ⁿ b ⁿ | n> = 0} is not regular, but you have no restrictions on p and q (I mean, it is not necessary to count both occurrences a and b).

However, a language is regular if and only if it can be expressed with a regular expression. And in this case you can do this: a * b *. Therefore, you can conclude that this language is regular.

Edit: for p <= q, the language is not regular, but you are considering any p and q.