Register

Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)

226 views
0 votes
0 votes
If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that
$A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz|for some y,|x|=|y|=|z| and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}-\frac{1}{3}}$ is not necessarily regular.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
admin asked Apr 30, 2019
259 views
Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}-}.$
If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$...
User Avatar
2 votes
2 votes
2 answers
3
admin asked Apr 30, 2019
512 views
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
Let $\sum = \{0,1\}$Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular.Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}....
User Avatar
Link Copied!