The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
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
0
answers
1
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 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

31
views
michaelsipser
theoryofcomputation
regularexpressions
decidability
proof
0
votes
0
answers
2
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
Veteran
(
59.1k
points)

19
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
decidability
proof
0
votes
1
answer
3
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 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

49
views
cmi2019
regularexpressions
regularlanguages
nfadfa
+1
vote
2
answers
4
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 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

71
views
cmi2018
regularlanguages
regularexpressions
easy
0
votes
0
answers
5
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 6, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

31
views
ullman
compilerdesign
syntaxdirectedtranslation
regularexpressions
nfadfa
parser
0
votes
0
answers
6
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
Veteran
(
59.1k
points)

24
views
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
7
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
Veteran
(
59.1k
points)

35
views
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
8
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

22
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
9
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127  128)
asked
Aug 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

21
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
10
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

17
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
11
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

8
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
12
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

13
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
13
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

2
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
14
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

4
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
15
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

8
views
ullman
compilerdesign
regularexpressions
lexeme
descriptive
0
votes
1
answer
16
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 5, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

64
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
1
answer
17
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
Veteran
(
59.1k
points)

141
views
michaelsipser
theoryofcomputation
regularexpressions
finiteautomata
0
votes
1
answer
18
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
Veteran
(
59.1k
points)

141
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
19
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
Veteran
(
59.1k
points)

52
views
michaelsipser
theoryofcomputation
regularlanguages
regularexpressions
0
votes
1
answer
20
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
Veteran
(
59.1k
points)

96
views
michaelsipser
theoryofcomputation
regularexpressions
nfadfa
0
votes
1
answer
21
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 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

102
views
michaelsipser
theoryofcomputation
regularexpressions
0
votes
0
answers
22
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 14, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

31
views
peterlinz
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
23
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
Veteran
(
59.1k
points)

21
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
24
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
Veteran
(
59.1k
points)

18
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
25
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
Veteran
(
59.1k
points)

18
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
26
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
Veteran
(
59.1k
points)

11
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
27
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
Veteran
(
59.1k
points)

21
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
28
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
Veteran
(
59.1k
points)

18
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 4.2 Question 10 (Page No. 149)
Suppose that $L$ is any language not necessarily regular whose alphabet is $\{0\};$i.e. the strings of $L$ consist of $0's$ only. Prove that $L^{*}$ is regular. Hint$:$ At first this theorem sounds preposterous. However, an example will help you see why ... ,use copy of $000$ and $(j3)/2$ copies of $00.$ Thus ,$L^{*}=$ $\in + 000^{*}.$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

11
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 4.2 Question 9 (Page No. 148  149)
We can generalize question $8$ to a number of functions that determine how much of the string we take.If $f$ is a function of integers, define $f(L)$ to be $\text{\{w for some $x,$ with $x=f(w)$,we have $ ... what we do not take. $f(n)=2^{n}(i.e,$ what we take has length equal to the logarithm of what we leave$).$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.1k
points)

14
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged regularexpressions
Recent Blog Comments
Yes and few more questions also
nkg_master9 you challenged that dbms query...
@nsaisirisha Yes they will give marks only...
When will the results be declared based on...
For the questions with two answers as per the...
50,737
questions
57,339
answers
198,449
comments
105,205
users