Regular/Non Regular (adding powers to 100 or more)

zulfi100

Joined Jun 7, 2012
629
Hi,
Some body please tell me if the following expression regular or not?

Q1. {a^n b^m | n + m >= 100}

Q2. {a^n b ^ (m+n) | n, m >= 0}

Confusing some finite values possible but Non-regular, because powers can be infinite; if n==0, m >= 100; if n==1, m>=99; if n==2, m>=98 and so on.

Is there any difference between (1) & (2) or both same?

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
You really need to stop talking about "powers" -- the superscript notation is NOT an exponent. It indicated repeated concatenation, nothing more.

Yes the is a difference between (1) and (2).

Is "aaabbbbb" in both languages, or just one?

Is a^90 b^10 in both languages, or just one?

zulfi100

Joined Jun 7, 2012
629
You really need to stop talking about "powers" -- the superscript notation is NOT an exponent. It indicated repeated concatenation, nothing more.

Yes the is a difference between (1) and (2).

Is "aaabbbbb" in both languages, or just one?

Is a^90 b^10 in both languages, or just one?
Hi,
Is "aaabbbbb" in both languages, or just one?
Only in Language related to Q2. For language related to Q1 (n+m) should be greater than or equal to 0.
Is a^90 b^10 in both languages, or just one?
Only in language related to Q1. where n=90 & m=10. For language related to Q2 b must be repeated more than n times.

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
Is "aaabbbbb" in both languages, or just one?
Only in Language related to Q2. For language related to Q1 (n+m) should be greater than or equal to 0.
Is a^90 b^10 in both languages, or just one?
Only in language related to Q1. where n=90 & m=10. For language related to Q2 b must be repeated more than n times.
So there IS a difference between the languages and they are not the same. But more importantly, do you see how you can establish that they are not the same? You look at the definitions and try to construct a string that is in one of the languages and not in the other. It usually isn't too difficult to do so if they are, in fact, different.

What are the tools that you have available to determine (and prove) either that a language is regular, or that it is not?

zulfi100

Joined Jun 7, 2012
629
So there IS a difference between the languages and they are not the same. But more importantly, do you see how you can establish that they are not the same? You look at the definitions and try to construct a string that is in one of the languages and not in the other. It usually isn't too difficult to do so if they are, in fact, different.

What are the tools that you have available to determine (and prove) either that a language is regular, or that it is not?
Tool is
So there IS a difference between the languages and they are not the same. But more importantly, do you see how you can establish that they are not the same? You look at the definitions and try to construct a string that is in one of the languages and not in the other. It usually isn't too difficult to do so if they are, in fact, different.

What are the tools that you have available to determine (and prove) either that a language is regular, or that it is not?
DFA. I got one link at:
https://math.stackexchange.com/questions/282216/determine-if-a-language-is-regular-from-the-first-sight
I think Q(2) is regular because no relationship between the exponents.

Q1. We have to use counters so its not regular.

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
I think Q(2) is regular because no relationship between the exponents.
How do you get that there's no relationship between the exponents?

You've already indicated that L = aⁿbⁿ is not regular. If that's the case, then why how could aⁿbⁿb² be regular? If that's not regular, then how could replacing the 2 with m make it regular?

Q1. We have to use counters so its not regular.
It's not whether we have to count something, it's how we have to count something.

Is the language L = aⁿ | n > 3 regular? Don't we have to count something?

zulfi100

Joined Jun 7, 2012
629
How do you get that there's no relationship between the exponents?

You've already indicated that L = aⁿbⁿ is not regular. If that's the case, then why how could aⁿbⁿb² be regular? If that's not regular, then how could replacing the 2 with m make it regular?

It's not whether we have to count something, it's how we have to count something.

Is the language L = aⁿ | n > 3 regular? Don't we have to count something?
Hi,
<Is the language L = aⁿ | n > 3 regular? Don't we have to count something? >
Not regular. Because not finite.

Zulfi.

Last edited:

WBahn

Joined Mar 31, 2012
24,981
Hi,
<Is the language L = aⁿ | n > 3 regular? Don't we have to count something? >
Not regular. Because not finite.

Zulfi.
We've already established that languages do not need to be finite to be regular.

Is the language consisting of all strings that have an even number of a's regular or not?

If you say that it is regular, then you have just said that an infinite language is regular.

zulfi100

Joined Jun 7, 2012
629
We've already established that languages do not need to be finite to be regular.
Excuse me, we did not. We said some thing opposite like:
So if there are a finite number of ways that have to be considered, what does that mean as far as the ability to construct a DFA?

Is the language consisting of all strings that have an even number of a's regular or not?

If you say that it is regular, then you have just said that an infinite language is regular.
Sorry we have not yet decided about a^n, if a^n b^n is not regular then why a^n is regular?

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
Excuse me, we did not. We said some thing opposite like:
So if there are a finite number of ways that have to be considered, what does that mean as far as the ability to construct a DFA?
You are once again falling for the fallacy of the converse.

Just because all finite languages are regular does NOT mean that all regular languages are finite.

Furthermore, even that case you are referring to was an infinite language. It's just that there were finite many short strings that had to be excluded from it.

Sorry we have not yet decided about a^n, if a^n b^n is not regular then why a^n is regular?
The language L = {aⁿ | n ≥ 0} is nothing more than a* -- or the language consisting of all strings having zero or more a's and nothing else.

You really don't see how you could construct a DFA to accept that language?

zulfi100

Joined Jun 7, 2012
629
You are once again falling for the fallacy of the converse.

Just because all finite languages are regular does NOT mean that all regular languages are finite.

Furthermore, even that case you are referring to was an infinite language. It's just that there were finite many short strings that had to be excluded from it.

The language L = {aⁿ | n ≥ 0} is nothing more than a* -- or the language consisting of all strings having zero or more a's and nothing else.

You really don't see how you could construct a DFA to accept that language?
Thanks a lot. I know the meaning of language. DFA can be constructed by using a single state where all a's are going and similarly we can construct a DFA for a^n. b^n but this time, all a's and b's would be going to that single state. But this is not regular where as a^n is regular. Please guide me this disparity.

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
Thanks a lot. I know the meaning of language. DFA can be constructed by using a single state where all a's are going and similarly we can construct a DFA for a^n. b^n but this time, all a's and b's would be going to that single state. But this is not regular where as a^n is regular. Please guide me this disparity.

Zulfi.
The language aⁿbⁿ is not regular because once you get reading all of the a's your machine has to be remembering exactly how many a's is saw so that it can match that to the number of b's that it is about to start seeing. But the only memory that a DFA has it what state it is currently in. So it would need a state that told it that there were 17 a's in the string and it would need a different state that told it that there were 1,763,294 a's in the string.

So how many states would the machine need in order to be capable of handing every possible string that might be presented to it?

Now consider what the "finite" in "finite automaton" is referring to -- an automaton consisting of a finite set of states.

zulfi100

Joined Jun 7, 2012
629
The language aⁿbⁿ is not regular because once you get reading all of the a's your machine has to be remembering exactly how many a's is saw so that it can match that to the number of b's that it is about to start seeing. But the only memory that a DFA has it what state it is currently in. So it would need a state that told it that there were 17 a's in the string and it would need a different state that told it that there were 1,763,294 a's in the string.
This means if there are 17 a's then we would have a special state to keep the value 17, I don't thing we do this in automata? How can we store integer values in a state?

Zulfi.

WBahn

Joined Mar 31, 2012
24,981
This means if there are 17 a's then we would have a special state to keep the value 17, I don't thing we do this in automata? How can we store integer values in a state?

Zulfi.
Where not storing anything in the state, it's that very fact that the machine is in that state that indicates the information. Imagine a machine for the language L = aaa(a*) -- i.e., all strings consisting of nothing but a's and starting with at least three a's. We might have the start state (q0) followed by q1, q2, q3, and q4 plus a trap state qx. If we are in q2 the very fact that we are in q2 means that we have seen exactly two leading a's thus far.

So if we had L = aⁿbⁿ | n < 1000, we could do this with a DFA because we could have one state that means that we have seen 17 a's, another state that means we have seen 731 a's, an other state that means we have matched b's against all but the first 13 a's, and so forth. Our machine would have about 2000 states in it. But if we remove the restriction on n, now our machine would need an infinite number of states, which is neither possible nor allowed.

zulfi100

Joined Jun 7, 2012
629
Where not storing anything in the state, it's that very fact that the machine is in that state that indicates the information. Imagine a machine for the language L = aaa(a*) -- i.e., all strings consisting of nothing but a's and starting with at least three a's. We might have the start state (q0) followed by q1, q2, q3, and q4 plus a trap state qx. If we are in q2 the very fact that we are in q2 means that we have seen exactly two leading a's thus far.
So if we had L = aⁿbⁿ | n < 1000, we could do this with a DFA because we could have one state that means that we have seen 17 a's, another state that means we have seen 731 a's, an other state that means we have matched b's against all but the first 13 a's, and so forth. Our machine would have about 2000 states in it.
Yes. Good. So 'n' n<1000, would make the machine regular?
as compared to L = aⁿbⁿ | n >= 0, which is not regular.
But if we remove the restriction on n, now our machine would need an infinite number of states, which is neither possible nor allowed.
But L=a^n | n>=0 is still regular, and similarly L=w | w is a set of even numbers, is also regular.
Kindly guide me.
Zulfi

WBahn

Joined Mar 31, 2012
24,981