The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
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
(
36.4k
points)

30
views
michaelsipser
theoryofcomputation
regularexpressions
finiteautomata
0
votes
1
answer
2
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
(
36.4k
points)

25
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
3
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
(
36.4k
points)

12
views
michaelsipser
theoryofcomputation
regularlanguages
regularexpressions
0
votes
1
answer
4
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
(
36.4k
points)

15
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
0
votes
1
answer
5
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
(
36.4k
points)

28
views
michaelsipser
theoryofcomputation
regularexpressions
0
votes
0
answers
6
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
(
12.1k
points)

20
views
peterlinz
theoryofcomputation
grammar
regularexpressions
0
votes
0
answers
7
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
(
36.4k
points)

15
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
8
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
(
36.4k
points)

9
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
9
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
(
36.4k
points)

10
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
10
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
(
36.4k
points)

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

14
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
12
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
(
36.4k
points)

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

8
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
14
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
(
36.4k
points)

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

13
views
ullman
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
16
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
(
36.4k
points)

12
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
17
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
(
12.1k
points)

9
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
18
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
(
36.4k
points)

22
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 4.2 Question 5 (Page No. 148)
The operation of Problem $4.2.3$ is sometimes viewed as a $"$derivative and $a/L$ is written $\frac{dL}{da}.$ These derivatives apply to regular expressions in a manner similar to the way ordinary derivatives apply to arithmetic ... $\frac{dL}{d0}=\phi$ Characterize those languages $L$ for which $\frac{dL}{d0}=L$
asked
Apr 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

10
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 3.2 Question 17 (Page No. 89)
Analogous to the previous exercise, consider all words that can be formed from $L$ by dropping a single symbol of the string. Formally define this operation drop for languages. Construct an nfa for $drop (L)$, given an nfa for $L$.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.1k
points)

12
views
peterlinz
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 3.2 Question 16 (Page No. 89)
In some applications, such as programs that check spelling, we may not need an exact match of the pattern, only an approximate one. Once the notion of an approximate match has been made precise, automata theory can be applied to ... this to write a patternrecognition program for $insert (L)$, using as input a regular expression for $L$.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.1k
points)

5
views
theoryofcomputation
peterlinz
regularexpressions
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 3.2 Question 15 (Page No. 89)
Write a regular expression for the set of all $C$ real numbers.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.1k
points)

5
views
theoryofcomputation
peterlinz
regularexpressions
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 3.2 Question 13 (Page No. 88)
Find a regular expression for the following languages on {$a, b$}. (a) $L =$ {$w : n_a (w)$ and $n_b (w)$ are both even}. (b) $L =$ {$w :(n_a (w)  n_b (w))$ mod $3 = 1$}. (c) $L =$ {$w :(n_a (w)  n_b (w))$ mod $3 = 0$}. (d) $L =$ {$w :2n_a (w)+3n_b (w)$ is even}.
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
12.1k
points)

8
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 3.4 Question 4 (Page No. 123)
Prove that $(L^{*}M^{*})^{*}=(L+M)^{*}.$Complete the proof by showing that strings in $(L^{*}M^{*})^{*}$ are also in $(L+M)^{*}.$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

14
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 3.4 Question 3 (Page No. 122)
We developed the regular expression $(0+1)^{*}1(0+1)+(0+1)^{*}1(0+1)(0+1)$ Use the distributive laws to develop two different,simpler,equivalent expressions.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

16
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 3.4 Question 2 (Page No. 122)
Prove or disprove each of the following statements about regular expressions. $(R+S)^{*}=R^{*}+S^{*}$ $(RS+R)^{*}R=R(SR+R)^{*}$ $(RS+R)^{*}RS=(RR^{*}S)^{*}$ $(R+S)^{*}S=(R^{*}S)^{*}$ $S(RS+S)^{*}R=RR^{*}S(RR^{*}S)^{*}$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

33
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 3.4 Question 1 (Page No. 121  122)
Verify the following identities involving regular expressions. $R+S=S+R$ $(R+S)+T=R+(S+T)$ $(RS)T=R(ST)$ $R(S+T)=RS+RT$ $(R+S)T=RT+ST$ $(R^{*})^{*}=R^{*}$ $(\in+R)^{*}=R^{*}$ $(R^{*}S^{*})^{*}=(R+S)^{*}$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

27
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 3.3 Question 2 (Page No. 114)
Give a regular expression to represent salaries as they might appear in employment advertising. Consider that salaries might be given on a per hour, week, month or year basis. They may or may not appear with a dollar sign or ... classified ads in a newspaper, or online jobs listings to get an idea of what patterns might be useful.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

8
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 3.3 Question 1 (Page No. 114)
Give a regular expression to describe phone numbers in all the various forms you can think of. Consider international numbers as well as the fact that different countries have different numbers of digits in area codes and in local phone numbers.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

12
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
+1
vote
0
answers
30
Ullman (TOC) Edition 3 Exercise 3.2 Question 5 (Page No. 108)
Convert the following regular expressions to NFA's with $\in$transactions. $01^{*}$ $(0+1)01$ $00(0+1)^{*}$ Eliminate $\in$transactions from your $\inNFA’s$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

12
views
ullman
theoryofcomputation
regularexpressions
Page:
1
2
3
4
5
6
...
16
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 Intelligent Systems RA interview experience
COAP Round 2 may begin at 5PM Today
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
Follow @csegate
Recent questions tagged regularexpressions
Recent Blog Comments
Rank 464. OBC
Thanks for sharing your exp Naveen and congrats...
what is cross word question exactly
how you prepared for such tricky questions
please anyone who has idea of this reply
49,456
questions
53,658
answers
186,156
comments
70,919
users