MadeEasy Test Series: Theory Of Computation - Regular Expressions

Question

Consider the following statements:
S1: Infinite language with finite dependency is always regular.
S2: Regular expression 01*0 represent an infinite set of finite strings.
Which of the following is True about S1 and S2?

a). only S1 is True 
b). only S2 is True 
c). both S1 and S2 are True 
d). both S1 and S2 are False

Comments

@sudsho get it now. I was confused in infinite set of finite strings only.

---

Is the answer C) bro @mcjoshi??If yes let me know..I will explain

---

Yes, it is.

Answer 1

Here finite idependency needs to be understood properly.U can think it as finite number of constraints , for example a precedes b so re is a*b* which is regular but it is an infinite language.

But take an example of L = {a^m bⁿ  |  m = n}

Now the dependency does not remain finite since we do not know how many a's will come exactly and also here for each 'a' in the string each 'b' is required , so dependency is not finite here.

Hence statement 1 is correct.

Now we come to statement 2.

Length of a string has to be finite .There is no meaning of a string having infinite length.But yes it may contain infinite number of strings in the language.

Whenever we say a language is infinite , then it is actually referred to number of strings not the length of a string.

Hence C) is the correct option.

Comments

In first statement, dependency does not remain finite means that language is bounded (or) all the literals are finitely dependent on each other.

---

Yes that's why I m saying.Literals mean the individual term of the expression.

---

Means if we are able to find out some pattern in between alphabets of a language, then finite dependency exists and the language is regular.