Register

GO Classes DPP | TOC|RE

392 views
6 6 votes

Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string).

i. $0^* 1(0+1)^*$

ii. $(0+1)^* 10^*$

iii. $0^* 1^* 0^*$

iv. $(0+1)^* 1(0+1)^*$
(Select all that apply.)

  1. (i) and (ii)
     
  2. (i) and (iv)
     
  3. (ii) and (iii)
     
  4. (iii) and (iv)

3 Answers

2 2 votes
( iii ) can generate empty string and strings that do not contain '1' ;

i , ii and iv generate all the strings containing atleast one '1'.

So  i , ii and iv are equivalent to each other

Option A , B
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · GO Classes DPP | ML ...
← Previous in category · GO Classes DPP | TOC...Next in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

6 6 votes
1 1 answer
334
334 views
GO Classes asked Oct 10, 2025
334 views
GO Classes DPP | TOC|FA
Let $w$ be any string of length $n>1$ over the alphabet $\{0,1\}^*$. Let $L_p$ be the set of all nonempty prefixes of $w$ and $L_s$ be the set of all non-empty suffixes o...
7 7 votes
2 2 answers
327
327 views
GO Classes asked Oct 10, 2025
327 views
GO Classes DPP | TOC|FA
  The language accepted by this automaton is given by the regular expression$\left(b^* a\left(a b^* a\right)^* b+\varepsilon\right)(a+b b)^*$ $(a+b)^*$ $b^* a(a+b)^* b(a+...
5 5 votes
1 1 answer
403
403 views
GO Classes asked Oct 10, 2025
403 views
GO Classes DPP | TOC|GRAMMAR
Consider the following context-free grammar $G$ with start variable $S$ and terminals $a, b$:$$S \rightarrow a S b|S S| a b$$Which ONE of the following languages is gener...
3 3 votes
1 1 answer
296
296 views
GO Classes asked Oct 10, 2025
296 views
GO Classes DPP | TOC| GRAMMAR
Consider the following context-free grammar: $G$, where $S, A$, and $B$ are the variables (nonterminals), $a, b, c$, and $d$ are the terminal symbols, $S$ is the start va...