search
Log In
0 votes
48 views
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}-}.$
in Theory of Computation 48 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
29 views
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.
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 29 views
0 votes
0 answers
2
37 views
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 37 views
0 votes
0 answers
3
83 views
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $|s| < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $|s| < k1k2.$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 83 views
1 vote
1 answer
4
...