search
Log In

Recent questions tagged regular-expressions

4 votes
1 answer
1
​​​​​​​Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$
asked Feb 18 in Theory of Computation Arjun 918 views
0 votes
4 answers
2
Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively. Which of the following is true with respect to the two languages? $L_1 \subset L_2$ $L_2 \subset L_1$ $L_1 = L_2$ $L_1 \cap L_2 = \phi$
asked Nov 20, 2020 in Theory of Computation jothee 388 views
0 votes
2 answers
3
Consider the following regular expressions: $r=a(b+a)^*$ $s=a(a+b)^*$ $t=aa^*b$ Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above: $L(r) \subseteq L(s) \subseteq L(t)$ $L(r) \supseteq L(s) \supseteq L(t)$ $L(r) \supseteq L(t) \supseteq L(s)$ $L(s) \supseteq L(t) \supseteq L(r)$
asked Nov 20, 2020 in Theory of Computation jothee 257 views
0 votes
2 answers
4
0 votes
1 answer
5
Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 388 views
1 vote
2 answers
6
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 343 views
1 vote
2 answers
8
0 votes
7 answers
9
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 1.1k views
0 votes
3 answers
10
A regular expression is $(a+b^{\ast}c)$ is equivalent to set of strings with either $a$ or one or more occurrence of $b$ followed by $c$. $(b^{\ast}c+a)$ set of strings with either $a$ or zero or more occurrence of $b$ followed by $c$. Both (B) and (C)
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 825 views
0 votes
5 answers
11
What is the meaning of regular expression $\Sigma^*001\Sigma^*$? Any string containing ‘$1$’ as substring Any string containing ‘$01$’ as substring Any string containing ‘$011$’ as substring All string containing ‘$001$’ as substring
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 540 views
0 votes
2 answers
12
0 votes
2 answers
13
Which of the following is equivalent regular expressions? $((01)^*(10)^*)^*$ $(10+01)^*$ $(01)^*+(11)^*$ $(0^*+(11)^*+0^*)^*)$ (i) and (ii) (ii) and (iii) (iii) and (iv) (iv) and (i)
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 433 views
0 votes
1 answer
14
0 votes
2 answers
15
Which of the following strings would match the regular expression : $p+ [3-5] * [xyz]$? $p443y$ $p6y$ $3xyz$ $p35z$ $p353535x$ $ppp5$ I, IlI and VI only IV, V and VI only II, IV and V only I, IV and V only
asked Mar 24, 2020 in Theory of Computation jothee 364 views
9 votes
3 answers
16
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$
asked Feb 12, 2020 in Theory of Computation Arjun 9k views
0 votes
0 answers
17
Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a similar approach fail to show that $PREFIX-FREE_{CFG}$ is decidable?
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 192 views
1 vote
3 answers
19
Consider an alphabet $\Sigma=\{a,b\}.$ Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$ Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$ Give an example of a word in $L.$ Give an example of a word not in $L.$ Construct an NFA for $L.$
asked Sep 13, 2019 in Theory of Computation gatecse 509 views
2 votes
4 answers
20
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
asked Sep 13, 2019 in Theory of Computation gatecse 499 views
0 votes
0 answers
21
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an L-attributed SDD on a top-down parsable grammar. Assume that there is a token char representing any character, and that char.$lexval$ is the character it ... that is, a state never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
asked Sep 6, 2019 in Compiler Design Lakshman Patel RJIT 269 views
0 votes
0 answers
22
Repeat Exercise 4.3.1 on the following grammars: $S\rightarrow SS+\mid SS\: \ast\mid a$ $S\rightarrow 0S1\mid 01$ $S\rightarrow S ( S ) S\mid \epsilon$ $S\rightarrow (L)\mid a$ and $L\rightarrow L,S\mid S$ ... $bterm\rightarrow bterm\:and\:bfactor\mid bfactor$ $bfactor\rightarrow not\: bfactor\mid ( bexpr )\mid true \mid false $
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 215 views
0 votes
0 answers
23
The following is a grammar for regular expressions over symbols $a$ and $b$ only, using $+$ in place of $\mid$ for union, to avoid conflict with the use of vertical bar as a metasymbol in grammars: $rexpr\rightarrow rexpr+rterm\mid rterm$ ... -down parsing? In addition to left factoring, eliminate left recursion from the original grammar. Is the resulting grammar suitable for top-down parsing?
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 406 views
...