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.

 

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?

 

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.

What about regularity?

Zulfi.

 

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 about regularity?

What about it?

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

 

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 about it?

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 about it?

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/ques...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.

Is the above answer correct?

Zulfi.

 

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?

 

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.

 

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.

 

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?

https://forum.allaboutcircuits.com/...-the-language-is-regular.164474/#post-1447309

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.

 

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?
https://forum.allaboutcircuits.com/...-the-language-is-regular.164474/#post-1447309

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?

 

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.

 

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.

 

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.

 

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.

 

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.

Hi, I was thinking about this answer. But your explanation is wonderful

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

 

Hi, I was thinking about this answer. But your explanation is wonderful

Yes. Good. So 'n' n<1000, would make the machine regular?
as compared to L = aⁿbⁿ | n >= 0, which is not regular.

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

You do realize, I hope, that L = a^n | n >= 0 is exactly the same language as L = a*.

Again, it's not whether the language has an infinite number of strings, it's whether we can recognize each of the individual strings using a machine that has a finite number of states.

In the case of this language we only need to states. If we are in one state we know that we have no read any characters thus far that were not an 'a' and if we are in the other state we know that we have read at least one character thus far that is not an 'a'. That is ALL the information we need in order to decide whether any given string is in the language.