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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged regularexpressions
Materials needed
Stanford slides
Colostate slides
0
votes
0
answers
1
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

4
views
ullman
compilerdesign
syntaxdirectedtranslation
regularexpressions
nfa
parser
0
votes
0
answers
2
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

6
views
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
3
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

1
view
ullman
compilerdesign
regularexpressions
leftrecursion
descriptive
0
votes
0
answers
4
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

16
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
5
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127  128)
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

14
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
6
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

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

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

2
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
9
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

1
view
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
10
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

1
view
ullman
compilerdesign
regularexpressions
descriptive
0
votes
0
answers
11
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

2
views
ullman
compilerdesign
regularexpressions
lexeme
descriptive
0
votes
1
answer
12
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
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

13
views
ullman
compilerdesign
regularexpressions
descriptive
0
votes
1
answer
13
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

103
views
michaelsipser
theoryofcomputation
regularexpressions
finiteautomata
0
votes
1
answer
14
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

81
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
15
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

40
views
michaelsipser
theoryofcomputation
regularlanguages
regularexpressions
0
votes
1
answer
16
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

58
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
0
votes
1
answer
17
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

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

30
views
peterlinz
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
19
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

20
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
20
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

18
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
21
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

16
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
22
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

11
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
23
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

19
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
24
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

12
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
25
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

9
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
26
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
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

11
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 4.2 Question 8 (Page No. 148)
Let $L$ be a language.Define $\text{half(L)}$ to be the set of first halves of strings in $L,$ that is,$\{w\text{for some x such that x=w,we have wx in L}\}.$For example,if $L=\{\in,0010,011,010110\}$ then ... that oddlength strings do not contribute to $\text{half(L)}$Prove that if $L$ is a regular language,so is $\text{half(L)}.$
asked
Apr 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

15
views
ullman
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 4.2 Question 7 (Page No. 148)
If $w=a_{1}a_{2}.....a_{n}$ and $x=b_{1}b_{2}....b_{n}$ are strings of the same length, define $alt(w,x)$ to be the string in which the symbols of $w$ and $x$ alternate starting with $w$ ... in $L$ and $x$ is any string in $M$ of the same length. Prove that if $L$ and $M$ are regular,so is $alt(L,M).$
asked
Apr 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

14
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 4.1 Question 4 (Page No. 109)
Theorem 4.3 Let h be a homomorphism. If L is a regular language, then its homomorphic image h (L) is also regular. The family of regular languages is therefore closed under arbitrary homomorphisms. Proof: Let L be a regular language denoted by some ... 3, show that $h (r)$ is a regular expression. Then show that $h (r)$ denotes $h (L)$.
asked
Apr 4
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

15
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 4.2 Question 6 (Page No. 148)
Show that the regular languages are closed under the following operations$:$ $ min(L)=\big\{\text{ww is in L, but no proper prefix of w is in L}\big\}.$ $ min(L)=\big\{\text{ww is in L, and for no x other than $\in$ is wx in L}\big\}.$ $ init(L)=\big\{\text{w for some x, wx is in L}\big\}.$
asked
Apr 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

25
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Follow @csegate
Recent questions tagged regularexpressions
Recent Blog Comments
will pdfs be uploaded ?
6th...
Sir
4th...
49,984
questions
55,135
answers
190,487
comments
85,112
users