String

A string $w$ over an Alphabet $\Sigma$ is a finite sequence of symbols in $\Sigma$.

Example

If $\Sigma =\{a,b\}$, then ${\Sigma }^{\ast }$ includes $\epsilon$, which is the empty string (of length zero). We can also have $\text{a}$, $\text{ab}$, $\text{bababbbbaaaa}$.

Note

$\epsilon$ is not included in any alphabet (unless you explicitly specify it, of course). It is however a string over any alphabet. That is, $\epsilon \in {\Sigma }^{\ast }$, but $\epsilon \notin \Sigma$.

${\Sigma }^{\ast }$ is the set of all strings over $\Sigma$.

• This set is infinite, because it encompasses strings of all lengths.
• If $\Sigma$ has $m$ number of symbols, then there are $m^k$ number of strings of length $k$.

operations on strings

given strings $u$ and $v$, $u.v$ denotes their concatenation.

a string $u$ is a prefix of string $w$ if there exists a string $v$ such that $w=u.v$. for example, prefixes of the string $\text{aaba}$ include $ϵ$, $\text{a}$, $\text{aa}$, and $\text{aaba}$. similarly, a string $u$ is a suffix of string $w$ if there exists a string $v$ such that $w=v.u$.

notice that string $v$ can be $\epsilon$, the empty string. this means a string of length $k$ has $k+1$ possible suffixes and prefixes.

a string $u$ is a substring of $w$ if there exist strings $v$ and $v^{\prime }$ such that $w=v.u.v^{\prime }$.

Distinguishable strings

Two strings $u$ and $v$ are distinguishable with respect to a Language $A$ if there exists a string $w$ such that only one of $u.w$ and $v.w$ is in $A$.

Example

$\Sigma =\{\text{a, b}\}$ and $A_2=\{w\mid \text{second symbol in }w\text{ equals a}\}$

two distinguishable strings are $ϵ$ and $\text{a}$. if we add, for example, $\text{ba}$ to both strings, $ϵ.\text{ba}$ will be in $A_2$, but $\text{a.ba}$ will not be.

$\text{a}$ and $\text{b}$ are indistinguishable, because concatenating $w$ either rejects both, or accepts both. for all $w$, $\text{a}.w$ is in $A_2$ if and only if $\text{b}.w$ is in $A_2$.

this definition depends on the language $A$, but not any specific Automata for $A$.