Hi,
I have strings?
1) concatenation of 'a' zero or more times followed by 'b' i.e. a^ * b
2) concatenation of 'b'zero or more tmes followed by c+a i.e. b^* c+a
3) b+c followed by union of 'a' or 'b' in any order repeated for zero or more times i.e. b+c (a+b)^*

All of the above are combinations of finite and infinite strings. So how can we tell if they are regular or not?

Zulfi.

 

If you have a language that includes an infinite length string, then that string is beyond the capabilities of finite automatons, push-down automatons, or Turing machines to recognize. Each of these machines can only recognize strings that are finite in length. The number of strings in the language might (and usually is) infinite, but each individual string is of finite length.

Your third language definition is very ambiguously worded, but no reasonable interpretation matches the formal description you give, which is

L = b + (c · (a+b)* )

Remember the order of operations for the regular operators - Kleene state, then concatenation, then union.

 

If you have a language that includes an infinite length string, then that string is beyond the capabilities of finite automatons, push-down automatons, or Turing machines to recognize. Each of these machines can only recognize strings that are finite in length. The number of strings in the language might (and usually is) infinite, but each individual string is of finite length.

Your third language definition is very ambiguously worded, but no reasonable interpretation matches the formal description you give, which is

L = b + (c · (a+b)* )

Remember the order of operations for the regular operators - Kleene state, then concatenation, then union.

1) b, ab, aab, aaab (infinite strings but each string is of finite length, so its regular)
2) c, a, bc, ca, ac, bca, abc, bbca, abbc (infinite strings but each string is of finite length, so its regular)
3)b, c, bc, cb, bc, bca,bcb, bcab, bcba (infinite strings but each string is of finite length, so its regular)

Some body please check if all the strings are correct or not and the regularity answer is correct or not.

Zulfi.

 

It's not whether the strings are finite length or not that determines whether it is regular. ALL languages (in the context of these machines) are defined as being a set of finite length strings.

Consider the language

ab, aabb, aaabbb, aaaabbbb, .... By your reasoning, since there are an infinite number of strings but each string is of finite length, it's regular. But we know that this language isn't.

You still don't seem to understand what languages are and how they relate to the machines we are talking about.

A language is a set of strings that obey some rules that define the patterns that must be met in order to be included in the set. A machine capable of recognizing the language must, for ANY string that is presented to it, correctly accept all strings that meet the pattern requirements and never accept strings that don't. Different types of machines have different abilities to determine whether the required pattern has been met. Some rules are simply too complicated for the simpler machines to be able to accept all strings that it should while never accepting any string that it shouldn't.

 

It's not whether the strings are finite length or not that determines whether it is regular. ALL languages (in the context of these machines) are defined as being a set of finite length strings.

Consider the language

ab, aabb, aaabbb, aaaabbbb, .... By your reasoning, since there are an infinite number of strings but each string is of finite length, it's regular. But we know that this language isn't.

You still don't seem to understand what languages are and how they relate to the machines we are talking about.

A language is a set of strings that obey some rules that define the patterns that must be met in order to be included in the set. A machine capable of recognizing the language must, for ANY string that is presented to it, correctly accept all strings that meet the pattern requirements and never accept strings that don't. Different types of machines have different abilities to determine whether the required pattern has been met. Some rules are simply too complicated for the simpler machines to be able to accept all strings that it should while never accepting any string that it shouldn't.

Hi,
Thanks for your reply.
Do you mean that non-regular strings not accepted by DFA/NFA?

Consider the language

ab, aabb, aaabbb, aaaabbbb, .... By your reasoning, since there are an infinite number of strings but each string is of finite length, it's regular. But we know that this language isn't.

Please discuss the strings which I have mentioned so that I can understand my problem. I know you are talking about a^nb^n
[/QUOTE}
Zulfi.

 

You falling for yet another common fallacy. There is no such thing as a regular or non-regular string. A string is just a string. Regular versus non-regular is a property of a SET of strings.

For instance, is the string "abbabba" regular or non-regular? It's a palindrome and we know that the language consisting of all palindromes is non-regular. But it also has an odd number of a's and an even number of b's and we know that that language is regular.