Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged regular-expression
0
votes
0
answers
121
Michael Sipser Edition 3 Exercise 4 Question 22 (Page No. 212)
Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a similar approach fail to show that $PREFIX-FREE_{CFG}$ is decidable?
admin
asked
in
Theory of Computation
Oct 17, 2019
by
admin
397
views
michael-sipser
theory-of-computation
regular-expression
decidability
proof
0
votes
0
answers
122
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
504
views
michael-sipser
theory-of-computation
finite-automata
regular-expression
decidability
proof
3
votes
3
answers
123
CMI2019-B-1
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.$
gatecse
asked
in
Theory of Computation
Sep 13, 2019
by
gatecse
1.6k
views
cmi2019
regular-expression
regular-language
finite-automata
4
votes
4
answers
124
CMI2018-A-1
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
gatecse
asked
in
Theory of Computation
Sep 13, 2019
by
gatecse
1.0k
views
cmi2018
regular-language
regular-expression
easy
0
votes
0
answers
125
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 L-attributed SDD on a top-down 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$.
admin
asked
in
Compiler Design
Sep 6, 2019
by
admin
827
views
ullman
compiler-design
syntax-directed-translation
regular-expression
finite-automata
parsing
0
votes
0
answers
126
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 $
admin
asked
in
Compiler Design
Aug 20, 2019
by
admin
641
views
ullman
compiler-design
regular-expression
left-recursion
descriptive
0
votes
0
answers
127
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 top-down parsing?
admin
asked
in
Compiler Design
Aug 20, 2019
by
admin
1.5k
views
ullman
compiler-design
regular-expression
left-recursion
descriptive
0
votes
0
answers
128
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 percent-sign (%) 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.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
344
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
129
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127 - 128)
The UNIX shell command sh uses the operators in Fig. $3.9$ in filename expressions to describe sets of file names. For example, the filename expression *.o matches all filenames ending in. ... expressions can be replaced by equivalent regular expressions using only the basic union, concatenation, and closure operators.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
507
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
130
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?
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
303
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
131
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.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
252
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
132
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.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
789
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
133
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 "\.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
290
views
ullman
compiler-design
regular-expression
descriptive
0
votes
0
answers
134
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$.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
1.2k
views
ullman
compiler-design
regular-expression
descriptive
2
votes
0
answers
135
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 5 (Page No. 125 - 126)
Write regular definitions for the following languages: All strings of lowercase letters that contain the five vowels in order. All strings of lowercase letters in which the letters are in ascending lexicographic order. ... substring abb. All strings of a's and b's that do not contain the subsequence abb.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
2.4k
views
ullman
compiler-design
descriptive
regular-expression
1
vote
0
answers
136
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 case-insensitive language. Illustrate the idea by writing the expression for "select" in SQL.
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
1.1k
views
ullman
compiler-design
regular-expression
compiler-tokenization
descriptive
2
votes
1
answer
137
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}.$
admin
asked
in
Compiler Design
Aug 5, 2019
by
admin
2.2k
views
ullman
compiler-design
regular-expression
descriptive
2
votes
1
answer
138
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.$
admin
asked
in
Theory of Computation
Apr 21, 2019
by
admin
4.2k
views
michael-sipser
theory-of-computation
regular-expression
finite-automata
2
votes
1
answer
139
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.
admin
asked
in
Theory of Computation
Apr 21, 2019
by
admin
8.0k
views
michael-sipser
theory-of-computation
finite-automata
regular-expression
1
vote
1
answer
140
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 members-a total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts. $a^{*}b^{*}$ $a(ba)^{*}b$ ... $aba\cup bab$ $(\epsilon\cup a)b$ $(a\cup ba\cup bb)\Sigma^{*}$
admin
asked
in
Theory of Computation
Apr 21, 2019
by
admin
2.1k
views
michael-sipser
theory-of-computation
regular-language
regular-expression
0
votes
1
answer
141
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 non-deterministic finite automata. $(0\cup 1)^{*}000(0\cup 1)^{*}$ $(((00)^{*}(11))\cup 01)^{*}$ $\phi^{*}$
admin
asked
in
Theory of Computation
Apr 21, 2019
by
admin
6.2k
views
michael-sipser
theory-of-computation
regular-expression
finite-automata
1
vote
1
answer
142
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}$
admin
asked
in
Theory of Computation
Apr 21, 2019
by
admin
7.3k
views
michael-sipser
theory-of-computation
regular-expression
0
votes
0
answers
143
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 14, 2019
by
Naveen Kumar 3
401
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
regular-expression
0
votes
0
answers
144
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\}.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
259
views
ullman
theory-of-computation
regular-expression
context-free-grammar
0
votes
0
answers
145
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 B|1B|\in$ Give leftmost and rightmost derivations of the following strings$:$ $00101$ $1001$ $00011$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
224
views
ullman
theory-of-computation
context-free-grammar
regular-expression
0
votes
0
answers
146
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 ... the product construction so the resulting DFA accepts the union of the languages of the two given DFA's.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
216
views
ullman
theory-of-computation
regular-language
regular-expression
1
vote
0
answers
147
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^{n-m}|n\geq m\geq 0\}$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
219
views
ullman
theory-of-computation
regular-language
regular-expression
0
votes
0
answers
148
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_{i-1}w_{i-1}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.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
185
views
ullman
theory-of-computation
regular-language
regular-expression
0
votes
0
answers
149
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 $\in-NFA$ for $cycle(L).$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
191
views
ullman
theory-of-computation
regular-language
regular-expression
0
votes
0
answers
150
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 ... use copy of $000$ and $(j-3)/2$ copies of $00.$ Thus ,$L^{*}=$ $\in + 000^{*}.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
150
views
ullman
theory-of-computation
regular-language
regular-expression
Page:
« prev
1
2
3
4
5
6
7
8
9
10
...
21
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged regular-expression
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...