Cheap and Secure Web Hosting Provider : See Now

Question on interpreting logical notation, relating to alphabets, theoretical comp sci

, , No Comments
Problem Detail: 

$\exists x \in \Sigma^* (t=sx)$

Have I interpreted the above into words correctly?:

"There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, where sigma contains string 't', which is a concatenation of string x and string s."

I'm not clear on how/whether t=xs is an alphabet.

Note: an earlier version of this question, with some errors, was posted at Math.SE.

Asked By : kjldfg
Answered By : Rick Decker

Since $t$ and $s$ aren't quantified, the expression $\exists x\in\Sigma^*\;(t=sx)$ is a predicate $P(s, t)$ in inputs $t$, and $s$. In other words, we could write $$ P(s, t)\stackrel{\text{def}}{\equiv}\exists x\in\Sigma^*\;(t=sx) $$ meaning "$P(s, t)$ is true if and only if there is a string $x$ over $\Sigma$ for which $t$ is the concatenation of $s$ and $x$". In answer to your question, $t=sx$ isn't an alphabet, but is a condition, namely that $t$ (a string) can be expressed as the string $s$ followed by the string $x$.

Look at some examples, with $\Sigma = \{a,b\}$,

  1. Is $P(a, abb)$ true? It is if we can find a string $x$ such that $abb=ax$. Obviously $x=bb$ works here, so $P(a, abb)$ is true.
  2. Is $P(ba, abb)$ true? It is if we can find a string $x$ such that $abb=bax$. There's no $x$ we can use here, so $P(ba, abb)$ is false.

In general, it's not hard to see that $P(s,t)$ can be interpreted as "$s$ is a prefix of $t$".

In a different universe of discourse, if $s, t, x$ were integers, can you see that $\exists x\in\mathbb{N}\;(t=sx)$ would mean that $s$ divides $t$?

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback