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
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

17
views
ullman
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
2
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

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

18
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
4
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

26
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
5
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

10
views
ullman
theoryofcomputation
regularlanguages
regularexpressions
+1
vote
0
answers
6
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

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

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

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

19
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
10
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

33
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
11
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

24
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
12
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

54
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
13
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

49
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
14
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

15
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
0
votes
0
answers
15
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

18
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
descriptive
+1
vote
0
answers
16
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

19
views
ullman
theoryofcomputation
regularexpressions
0
votes
0
answers
17
Ullman (TOC) Edition 3 Exercise 3.2 Question 4 (Page No. 108)
Convert the following regular expressions to NFA's with $\in$transactions. $01^{*}$ $(0+1)01$ $00(0+1)^{*}$
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

19
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
18
Ullman (TOC) Edition 3 Exercise 3.2 Question 3 (Page No. 107)
Convert the following DFA to a regular expression using the state elimination techniques.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

36
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 3.2 Question 2 (Page No. 107)
Here is a transition table for a DFA$:$ Give all the regular expressions $R_{ij}^{0}.$ Note$:$Think of state $q_{i}$ as if it were the state with integer number $i.$ ... automaton. Construct the transition diagram for the DFA and give a regular expression for its language by eliminating state $q_{2}.$
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

21
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
20
Ullman (TOC) Edition 3 Exercise 3.2 Question 1 (Page No. 107)
Here is a transition table for a DFA$:$ Give all the regular expressions $R_{ij}^{0}.$ Note$:$Think of state $q_{i}$ as if it were the state with integer number $i.$ ... automaton. Construct the transition diagram for the DFA and give a regular expression for its language by eliminating state $q_{2}.$
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

17
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
21
Ullman (TOC) Edition 3 Exercise 3.1 Question 4 (Page No. 92)
Give English descriptions of the languages of the following regular expressions$:$ $(1+\in)(00^{*}1)^{*}0^{*}$ $(0^{*}1^{*})^{*}000(0+1)^{*}$ $(0+10)^{*}1^{*}$
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

15
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
22
Ullman (TOC) Edition 3 Exercise 3.1 Question 3 (Page No. 92)
Write regular expressions for the following languages$:$ The set of all strings of $0's$ and $1's$ not containing $101$ as a substring. The set of all strings with an equal number of $0's$ and $1's,$ such that no prefix has two more $0'$ ... of $0's$ and $1's$ whose number of $0's$ is divisible by five and whose number of $1's$ is even.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

15
views
ullman
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 3.1 Question 2 (Page No. 91)
Write regular expressions for the following languages$:$ The set of all strings of $0's$ and $1's$ such that every pair of adjacent $0's$ appears before any pair of adjacent $1's.$ The set of strings of $0's$ and $1's$ whose number of $0's$ is divisible by five.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

19
views
ullman
theoryofcomputation
finiteautomata
regularlanguages
regularexpressions
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 3.1 Question 1 (Page No. 91)
Write regular expressions for the following languages$:$ The set of strings over alphabet $\{a,b,c\}$ containing at least one $a$ and atleast one $b.$ The set of strings of $0's$ and $1's$ whose tenth symbol from the right end is $1.$ The set of strings of $0's$ and $1's$ with at most one pair of consecutive $1's.$
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

16
views
ullman
theoryofcomputation
finiteautomata
regularlanguages
regularexpressions
0
votes
1
answer
25
Peter Linz Edition 4 Exercise 3.2 Question 10 (Page No. 88)
Find regular expressions for the languages accepted by the following automata: https://gateoverflow.in/304714/peterlinzedition4exercise32question10bpageno88
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

34
views
peterlinz
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 3.2 Question 9 (Page No. 88)
What language is accepted by the following generalized transition graph?
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

19
views
theoryofcomputation
peterlinz
regularlanguages
regularexpressions
+1
vote
0
answers
27
Peter Linz Edition 4 Exercise 3.2 Question 8 (Page No. 87)
Consider the following generalized transition graph. (a) Find an equivalent generalized transition graph with only two states. (b) What is the language accepted by this graph?
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

19
views
peterlinz
theoryofcomputation
regularexpressions
regularlanguages
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 3.2 Question 7 (Page No. 87)
Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

8
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 3.2 Question 6 (Page No. 87)
Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

5
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 3.2 Question 5 (Page No. 87)
Find dfa's that accept the following languages. (a) $L = L (ab^*a^*)∪ L ((ab)^* ba)$. (b) $L = L (ab^*a^*) $ $\cap$ $L ((ab)^* ba)$.
asked
Apr 2, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

7
views
peterlinz
theoryofcomputation
regularlanguages
regularexpressions
Page:
« prev
1
2
3
4
5
6
7
...
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
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
Cut off will be between 95115 not more than that.
50,737
questions
57,384
answers
198,538
comments
105,332
users