Subword Sequence

Computer Science Level 1

Suppose we have two words written in the standard English alphabet, u u and v v . u u is a subword of v v , if some letters from v v can be deleted to obtain u u . For example, man is a subword of ma rti n , abb is a subword of a c b a b but cab is not a subword of bac kward.

True or False: In any infinite sequence of words, there are two words u u and v v such that u u is a subword of v v

For the purpose of this question, assume that a word is any finite sequence of letters from the English alphabet.

True False

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Louis Lebel
Jan 15, 2020

(Answering "in every infinite sequence of distinct words , each of finite length and solely composed of symbols from the standard English alphabet, is it possible to always find a a word and b a subword of a ?")

Let s be any lexicographically ordered sequence of infinitely many words (each of finite length).

First off, because there is a finite amount of symbols in the standard English alphabet (there are 26 letters), it can be said that s will necessarily run out of choices and will eventually have to come up with longer and longer words as we iterate over it.

Letting b be any word in s , and n be the length of b , we find that b can only be one in 26^n possibile words.

Considering this, it will only take 26^n new words for s to spit out a (any superword of b ). Therfore, s will necessarily contain a word and one of its subwords.

2 Helpful 1 Interesting 0 Brilliant 1 Confused

This is a consequence of Higman's Lemma:

Unfortunately, I do not know the proof of Higman's Lemma, but here is a pdf

3 Helpful 0 Interesting 0 Brilliant 2 Confused

Intuitively, it feels that if the sequence of words is infinite, then words are bound to repeat, in which case $u$ is a trivial subword of $v$. Without repeating words or, in some cases, before the word $u$ is repeated, we will surely have a word $v$, eventually, which will be a superword of $u$.

samvid mistry - 1 year, 8 months ago
A B
Jul 15, 2019

I think this might be worded wrong?

The problem is trivially solved by making

u := seq(1)

v := seq(1)+seq(2)

Don't you mean "for every given u there's a v"?

0 Helpful 0 Interesting 0 Brilliant 3 Confused

I am asking the question of whether every infinite sequence of words must have a pair of words u u and v v , such that u u is a subword of v v .

I do not understand your solution

Agnishom Chattopadhyay - 1 year, 11 months ago

Log in to reply

It seems to me the problem doesn't clearly define what this sequence is; for example, you could say that the words get concatenated, and I think this is what A B assumed. Other clarifications: Is a word a subword of itself? Are the u and v words from the sequence? I think they are, but you then say they are any finite sequence of letters from the alphabet.

Lucas Viana Reis - 1 year, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...