menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent Blog Comments
OFFTOPIC:- @Arjun sir why are the questions of...
Yep, the problem was the theme 😅. I can see...
@Ayush I think problem is because of dark theme,...
then only someone from the officials can help...
Nope, it doesn't. I have tried everything.
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
0
votes
83
views
Let $\sum = \{0,1\}$ and let $D = \{w|w$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$
Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.
michael-sipser
theory-of-computation
finite-automata
regular-languages
proof
descriptive
asked
Apr 30, 2019
in
Theory of Computation
Lakshman Patel RJIT
edited
Apr 30, 2019
by
Lakshman Patel RJIT
83
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
0
Answers
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
1
answer
1
90
views
Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
asked
Apr 30, 2019
in
Theory of Computation
Lakshman Patel RJIT
90
views
michael-sipser
theory-of-computation
finite-automata
regular-languages
proof
descriptive
0
votes
0
answers
2
282
views
Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROP-OUT(A) = $\{xz| xyz\in A$ where $x, ... $\text{Theorem 1.47.}$
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROP-OUT(A) = $\{xz| xyz\in A$ where $x, z\in\sum^{*},y\in\sum$\}}.$ Show ... is closed under the $\text{DROP-OUT}$ operation. Give both a proof by picture and a more formal proof by construction as in $\text{Theorem 1.47.}$
asked
Apr 30, 2019
in
Theory of Computation
Lakshman Patel RJIT
282
views
michael-sipser
theory-of-computation
finite-automata
regular-languages
proof
descriptive
0
votes
0
answers
3
44
views
Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
asked
Apr 30, 2019
in
Theory of Computation
Lakshman Patel RJIT
44
views
michael-sipser
theory-of-computation
finite-automata
regular-languages
proof
0
votes
0
answers
4
121
views
Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$ $\{0^{m}1^{n}|m\neq n\}$ $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtw|w,t\in\{0,1\}^{+}\}$
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$ $\{0^{m}1^{n}|m\neq n\}$ $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtw|w,t\in\{0,1\}^{+}\}$
asked
Apr 30, 2019
in
Theory of Computation
Lakshman Patel RJIT
121
views
michael-sipser
theory-of-computation
finite-automata
regular-languages
proof
...