42 votes 42 votes Which of the following statements is TRUE about the regular expression $01^*0$? It represents a finite set of finite strings. It represents an infinite set of finite strings. It represents a finite set of infinite strings. It represents an infinite set of infinite strings. Theory of Computation gateit-2005 theory-of-computation regular-expression easy + – Ishrat Jahan asked Nov 3, 2014 • edited Mar 3, 2018 by kenzou Ishrat Jahan 9.9k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Hemant Parihar commented Nov 22, 2017 reply Follow Share @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) 15 votes 15 votes Chhotu commented Nov 22, 2017 reply Follow Share Hi @Hemant Parihar ji, OK Thanks. Although wiki is not a very reliable source. 0 votes 0 votes air1ankit commented Dec 11, 2017 reply Follow Share anyone please explain above question 0 votes 0 votes Please log in or register to add a comment.
Best answer 66 votes 66 votes 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. Arjun answered Nov 4, 2014 • edited May 6, 2021 by soujanyareddy13 Arjun comment Share Follow See all 8 Comments See all 8 8 Comments reply Sandeep_Uniyal commented Jan 17, 2015 reply Follow Share @Arjun: you say a regular expression cant generate any "INFINITE STRING". Can any language do that !! But let me correct you here that "A string is always a FINITE sequence of symbols from the alphabet" except the empty string which is also a kind of finite. So when we say an infinite string that itself makes it incorrect. No language can generate a infinite string. Infact that is not said to be a string when sequence is not finite. So option (C) and (D) are eliminated with this only. 27 votes 27 votes learncp commented Jan 16, 2016 reply Follow Share @arjun sir, the above regex can be represented using a DFA, and as we know that any finite set can be represented by a DFA. so the answer should be finite no of finite length strings. Am I missing anything here ? 0 votes 0 votes kumar_sanjay commented Jan 31, 2017 reply Follow Share @ Arjun sir, give example of finite set of infinite strings. infinite set of infinite strings.??? 0 votes 0 votes saxena0612 commented Dec 19, 2017 reply Follow Share $RE=01^*0 \\ Set=[00 \ \color{Blue}{(|00|=2)},010 \ \color{Blue}{(|010|=3)},0110 \ \color{Blue}{(|0110|=4})....]$ 0 votes 0 votes rio commented Mar 20, 2018 reply Follow Share @kumar_sanjay string are finite set of symbols so there annot be a infnite set of infinite string. 0 votes 0 votes Deepak Poonia commented Dec 12, 2019 reply Follow Share 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 20 votes 20 votes svas7246 commented Jul 2, 2021 reply Follow Share Great explanation 1 votes 1 votes SougataSarkar commented Jul 26, 2022 reply Follow Share 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? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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 varunrajarathnam answered Aug 21, 2020 varunrajarathnam comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Jul 15, 2021 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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 arkaprabha1012 answered Aug 22, 2020 arkaprabha1012 comment Share Follow See all 0 reply Please log in or register to add a comment.