patternMinor
Don’t understanding argument on words of a certain form
Viewed 0 times
understandingargumentwordsformcertaindon
Problem
In my book they use the following argument which I don’t understand :
Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^$ such that $ L \subset m_1^...m_k^$. Now choose the minimum $n$ such that there exists $l_1,..., l_n$ such that every word of $L$ is a prefix of a word in $l_1^...l_n^*$.
Hence by the minimality of $n$ there exist a word $u \in L$ such that $u$ is not a prefix of a word in $l_1^...l_{n-1}^$.
What I don’t understand is why such an $u$ exist. I don’t see why the minimality of $n$ prove the existence of such an $u$...
For example if I take $L = ab^c^d$ then I think the minimal $n$ is $4$ with the words $l_1 = a, l_2 = b, l_3 = c, l_4 = d$ and in this case such an $u$ clearly does not exist.
So is my book wrong or I am completely missing something here ?
Thank you !
Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^$ such that $ L \subset m_1^...m_k^$. Now choose the minimum $n$ such that there exists $l_1,..., l_n$ such that every word of $L$ is a prefix of a word in $l_1^...l_n^*$.
Hence by the minimality of $n$ there exist a word $u \in L$ such that $u$ is not a prefix of a word in $l_1^...l_{n-1}^$.
What I don’t understand is why such an $u$ exist. I don’t see why the minimality of $n$ prove the existence of such an $u$...
For example if I take $L = ab^c^d$ then I think the minimal $n$ is $4$ with the words $l_1 = a, l_2 = b, l_3 = c, l_4 = d$ and in this case such an $u$ clearly does not exist.
So is my book wrong or I am completely missing something here ?
Thank you !
Solution
I think the book is right. In your example, the word $u=abcd$ satisfies the conditions: it is not a prefix of a word in $a^ b^ c^*$.
In general, I think that proof is valid. I'll try to explain why the minimality of $n$ proves the existence of such a word $u \in L$. If there did not exist such a word $u \in L$, then that would mean that every word $u \in L$ is a prefix of $l_1^ \cdots l_{n-1}^$, which in turn would mean that $n$ wasn't the minimum possible (we could have used $n-1$), which contradicts how $n$ was chosen in the second sentence. That's a contradiction. If you start from an assumption and derive a contradiction, then you can conclude that the assumption must have been wrong. In particular, the only alternative that remains possible is that there does exist such a word $u \in L$.
Put another way, there are only two possibilities: either there does exist such a word $u \in L$, or there doesn't. I've shown why the second choice is always impossible. That means the first choice must actually always be true.
In general, I think that proof is valid. I'll try to explain why the minimality of $n$ proves the existence of such a word $u \in L$. If there did not exist such a word $u \in L$, then that would mean that every word $u \in L$ is a prefix of $l_1^ \cdots l_{n-1}^$, which in turn would mean that $n$ wasn't the minimum possible (we could have used $n-1$), which contradicts how $n$ was chosen in the second sentence. That's a contradiction. If you start from an assumption and derive a contradiction, then you can conclude that the assumption must have been wrong. In particular, the only alternative that remains possible is that there does exist such a word $u \in L$.
Put another way, there are only two possibilities: either there does exist such a word $u \in L$, or there doesn't. I've shown why the second choice is always impossible. That means the first choice must actually always be true.
Context
StackExchange Computer Science Q#104999, answer score: 2
Revisions (0)
No revisions yet.