The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged regularexpressions
Materials needed
Stanford slides
Colostate slides
0
votes
2
answers
1
UGCNETJan2017II: 31
Which of the following strings would match the regular expression : $p+ [35] * [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
in
Theory of Computation
by
jothee

121
views
ugcnetjan2017ii
regularexpressions
theoryofcomputation
+7
votes
5
answers
2
GATE2020CS7
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
in
Theory of Computation
by
Arjun

3k
views
gate2020cs
regularexpressions
normal
theoryofcomputation
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 22 (Page No. 212)
Let $PREFIXFREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefixfree}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a similar approach fail to show that $PREFIXFREE_{CFG}$ is decidable?
asked
Oct 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

101
views
michaelsipser
theoryofcomputation
regularexpressions
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
asked
Oct 16, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

65
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
decidability
proof
0
votes
1
answer
5
CMI2019B1
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 14, 2019
in
Theory of Computation
by
gatecse

127
views
cmi2019
regularexpressions
regularlanguages
nfadfa
+2
votes
3
answers
6
CMI2018A1
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 14, 2019
in
Theory of Computation
by
gatecse

201
views
cmi2018
regularlanguages
regularexpressions
easy
0
votes
0
answers
7
Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 6 (Page No. 317)
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an Lattributed SDD on a topdown parsable grammar. Assume that there is a token char representing any ... never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
asked
Sep 7, 2019
in
Compiler Design
by
Lakshman Patel RJIT

74
views
ullman
compilerdesign
syntaxdirectedtranslation
regularexpressions
nfadfa
parsing
0
votes
0
answers
8
Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 2 (Page No. 216  217)
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$ ... $bterm\rightarrow bterm\:and\:bfactor\mid bfactor$ $bfactor\rightarrow not\: bfactor\mid ( bexpr )\mid true \mid false $
asked
Aug 20, 2019
in
Compiler Design
by
Lakshman Patel RJIT

62
views
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
9
Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 1 (Page No. 216)
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 ... to left factoring, eliminate left recursion from the original grammar. Is the resulting grammar suitable for topdown parsing?
asked
Aug 20, 2019
in
Compiler Design
by
Lakshman Patel RJIT

104
views
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
10
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 12 (Page No. 128)
SQL allows a rudimentary form of patterns in which two characters have special meaning: underscore (_) stands for any one character and percentsign (%) stands for any string of $0$ or more characters. In ... to express any SQL pattern as a regular expression, given that we know which character is the escape character.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

37
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
11
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127  128)
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

43
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
12
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 10 (Page No. 127)
The operator ^ matches the left end of a line, and \ ... operators by an equivalent expression that does not use either of these operators?
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

33
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
13
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 9 (Page No. 127)
The regular expression $r\{m, n\}$ matches from $m$ to $n$ occurrences of the pattern $r$. For example, $a [1, 5]$ matches a string of one to five a's. Show that for every regular expression containing repetition operators of this form, there is an equivalent regular expression without repetition operators.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

24
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
14
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 8 (Page No. 126  127)
In Lex, a complemented character class represents any character except the ones listed in the character class. We denote a complemented class by using ^ as the first character; this ... expression with complemented character classes, there is an equivalent regular expression without complemented character classes.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

68
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
15
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 7 (Page No. 126)
Note that these regular expressions give all of the following symbols (operator characters) a special meaning: \ " . ^ ... the regular expression \*\* also matches the string **. Write a regular expression that matches the string "\.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

20
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
16
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 6 (Page No. 126)
Write character classes for the following sets of characters: The first ten letters (up to "j" ) in either upper or lower case. The lowercase consonants. The "digits" in a hexadecimal number (choose either ... we shall discuss extensively in Section $3.5)$. The extended notation is listed in Fig.$3.8$.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

44
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
17
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 4 (Page No. 125)
Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexeme is very simple. However, some languages, like SQL, are case insensitive, so a keyword ... in a caseinsensitive language. Illustrate the idea by writing the expression for "select" in SQL.
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

60
views
ullman
compilerdesign
regularexpressions
lexeme
descriptive
0
votes
1
answer
18
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 2 (Page No. 125)
Describe the languages denoted by the following regular expressions: $a(a\mid b)^{\ast}a.$ $((\epsilon\mid a)b^{\ast})^{\ast}.$ $(a\mid b)^{\ast}a(a\mid b)(a\mid b).$ $a^{\ast}ba^{\ast}ba^{\ast}ba^{\ast}.$ $(aa\mid bb)^{\ast}((ab\mid ba)(aa\mid bb)^{\ast}(ab\mid ba)(aa\mid bb)^{\ast})^{\ast}.$
asked
Aug 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT

151
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
1
answer
19
Michael Sipser Edition 3 Exercise 1 Question 22 (Page No. 87)
In certain programming languages, comments appear between delimiters such as $\text{/#}$ and $\text{#/}.$ Let $C$ be the language of all valid delimited comment strings. A member of $C$ must begin with $\text{/#}$ ... $DFA$ that recognizes $C.$ b. Give a regular expression that generates $C.$
asked
Apr 22, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

272
views
michaelsipser
theoryofcomputation
regularexpressions
finiteautomata
0
votes
1
answer
20
Michael Sipser Edition 3 Exercise 1 Question 21 (Page No. 86)
Use the procedure described in $\text{Lemma 1.60}$ to convert the following finite automata to regular expressions.
asked
Apr 22, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

490
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 20 (Page No. 86)
For each of the following languages, give two strings that are members and two strings that are not membersa total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts. $a^{*}b^{*}$ $a(ba)^{*}b$ $a^{*}\cup b^{*}$ ... $aba\cup bab$ $(\epsilon\cup a)b$ $(a\cup ba\cup bb)\sum^{*}$
asked
Apr 22, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

95
views
michaelsipser
theoryofcomputation
regularlanguages
regularexpressions
0
votes
1
answer
22
Michael Sipser Edition 3 Exercise 1 Question 19 (Page No. 86)
Use the procedure described in $\text{Lemma 1.55}$ to convert the following regular expressions to nondeterministic finite automata. $(0\cup 1)^{*}000(0\cup 1)^{*}$ $(((00)^{*}(11))\cup 01)^{*}$ $\phi^{*}$
asked
Apr 22, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

336
views
michaelsipser
theoryofcomputation
regularexpressions
nfadfa
0
votes
1
answer
23
Michael Sipser Edition 3 Exercise 1 Question 18 (Page No. 86)
Give regular expressions generating the languages of the alphabet is $\{0,1\}.$ $\text{\{w w begins with a 1 and ends with a 0\}}$ $\text{\{w w contains at least three 1s\}}$ ... $\text{The empty set}$ $\text{All strings except the empty string}$
asked
Apr 22, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

209
views
michaelsipser
theoryofcomputation
regularexpressions
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 5.2 Question 10 (Page No. 145)
Give an unambiguous grammar that generates the set of all regular expressions on $Σ =$ {$a,b$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

54
views
peterlinz
peterlinzedition4
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 5.1 Question 5 (Page No. 182)
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only difference is that we use $e$ for symbol $\in,$ to avoid potential ... Your task is to design a CFG with set of terminals $T$ that generates exactly the regular expressions with alphabet $\{0,1\}.$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

55
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 5.1 Question 2 (Page No. 182)
The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$ $S\rightarrow A1B$ $A\rightarrow 0A\in$ $B\rightarrow B1B\in$ Give leftmost and rightmost derivations of the following strings$:$ $00101$ $1001$ $00011$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

36
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 4.2 Question 14 (Page No. 149  150)
We described the $"$product construction$"$ that took two DFA's and constructed one DFA whose language is intersection of the languages of the first two. Show how to perform the product construction on NFA's ... the product construction so the resulting DFA accepts the union of the languages of the two given DFA's.
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

30
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 4.2 Question 13 (Page No. 149)
We can use closure properties to help prove certain languages are not regular. Start with the fact that the language $L_{0n1n}=\{0^{n}1^{n}n\geq 0\}$ is not a regular set. Prove the following languages not to be regular by transforming them using operations known to ... $\{0^{n}1^{m}2^{nm}n\geq m\geq 0\}$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

22
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 4.2 Question 12 (Page No. 149)
Let $w_{1}=a_{0}a_{0}a_{1},$ and $w_{i}=w_{i1}w_{i1}a_{i}$ for all $i>1.$For instance,$w_{3}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{3}.$ The shortest ... is $O(n^{2}).$ Find such an expression. Hint $:$ Find $n$ languages, each with regular expressions of length $O(n).$ Whose intersection is $L.$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 4.2 Question 11 (Page No. 149)
Show that the regular languages are closed under the following operation$:$ $\text{cycle(L)={we can write w as w = xy,such that yx is in L}}.$ For example if $L=\{01,011\},$then $cycle(L)=\{01,10,011,110,101\}.$ Hint$:$ Start with a DFA for $L$ and construct an $\inNFA$ for $cycle(L).$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

35
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
Page:
1
2
3
4
5
6
...
17
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged regularexpressions
Recent Blog Comments
After the written exam and at the time of...
Q1. I don't know any trick or method, I usually...
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,580
answers
201,986
comments
95,396
users