GATE IT 2005 | Question: 5

Question

Which of the following statements is TRUE about the regular expression $01^*0$?

• A. It represents a finite set of finite strings.
• B. It represents an infinite set of finite strings.
• C. It represents a finite set of infinite strings.
• D. It represents an infinite set of infinite strings.

Comments

@chhotu ji, See the Wikipedia definition of a string.

In formal language theory, a string is defined as a finite sequence of members of an underlying base set; this set is called the alphabet of a string or collection of strings.

P.S: https://en.wikipedia.org/wiki/Alphabet_(formal_languages)

---

 Hi @Hemant Parihar ji,

OK Thanks. Although wiki is not a very reliable source.

---

anyone please explain above question

Answer 1

Correct Option: B

Infinite set (because of $^*$) of finite strings. A string is defined as a FINITE sequence of characters and hence can never be infinite. 

Comments

We study Automata over finite strings in basic TOC course...All the machines that we study (FA,PDA,TM etc ) are defined over finite string input.

There are automata over infinite length strings as well. Buchi studied Automata over infinite length strings and it is known as Buchi Automata and it has many applications in giving decision procedure for validity of some first order logic formulas etc.

The automata that we’re studying are defined in such a way that they process only finite strings. People have defined and studied automata that process infinite strings, but they are a significantly more advanced topic.

Moreover, coming to this question, Kleene star(kleene closure) operation is defined in such a way that it only produces finite length strings. 

If $a$ is a symbol then kleene closure of $a$ is defined as : $a^* = \bigcup_{n \geq 0} a^n$

Where $a^0 = \in ; a^{n+1} = a.a^n$

Clearly, all the strings in $a^*$ will be of finite length (of some length $k$ for some non-negative integer $k$)

Since, there is no infinite integer, so each string is finite, but there are infinitely many strings in $a^*.$

https://math.stackexchange.com/questions/1425011/does-the-kleene-closure-of-an-alphabet-contain-an-infinite-string/1425014

---

Great explanation

---

Suppose IF1, IF2, IF3, IF4, ….. be some infinite languages then if we generate 2 languages L1 and L2 such that :-

L1 = { IF1, IF2, IF3, IF4, …...} ; then can we say L1 is a infinite set of infinite strings/ members?

L2 = { IF1 } ; then can we say L2 is a finite set of infinite strings/ members?

Answer 2

The given expression01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.

 

Optins B is correct

Comments

 

The given expression01*0 is regular. So this is a finite string

The expression is regular it’s ok but this is not the reason for the string to be finite.

Whatever a string can never be infinite. Correct me if I’m wrong.

Answer 3

string can be of infinite length but if it is recognised by finite automaton then this is finite so i think infinite number of strings are possible but the string length will be finite as it can be represented by the finite automaton so ans B