Register

CMI2015-B-01

• edited by
526 views
1 votes
1 votes
Let $\Sigma=\{a,b\}.$ Given a language $L\underline\subset \Sigma^{\ast}$ and a word $w\in\Sigma^{\ast}$, define the languages:
$$Extend(L,w) :=\{xw\:|\:x\in L\}$$ $$Shrink(L,w) :=\{x\:|\:xw\in L\}$$Show that if $L$ is regular, both $Extend(L,w)$ and $Shrink(L,w)$ are regular.
• edited by
User Avatar

1 Answer

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

Related questions

7 votes
7 votes
2 answers
2
go_editor asked May 27, 2016
1,467 views
CMI2015-A-01
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes-for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes. Let $\text{TwinPrime}(n)$ ... $\exists m \cdot \forall n \cdot \text{TwinPrime}(n) \text{ implies }n \leq m$
Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes—for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that th...
User Avatar
4 votes
4 votes
2 answers
4
go_editor asked May 27, 2016
716 views
CMI2015-B-06c
Consider the code below, defining the functions $f$ and $g$: f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n == 0) return m; else { q = m div 10; r = m mod 10; return g(f(f(q, 0), r), n-1); } } How much time does it take to compute $f(m, n)$ and $g(m, n)$?
Consider the code below, defining the functions $f$ and $g$:f(m, n) { if (m == 0) return n; else { q = m div 10; r = m mod 10; return f(q, 10*n + r); } } g(m, n) { if (n ...
User Avatar
Link Copied!