Notes

Definition: A string over $x,$ where $x$ is a finite set, is a finite sequence of elements from $x.$

In other words, a string is a finite sequence of characters. In programming languages, strings can be used to denote text.

The null string is the string with no elements. It is denoted $.$

$x^{**}$ is the set of all strings over $x.$

$x^{+}$is the set of all nomull strings over $x.$

The length of a string $$ is the number of elements in $.$ It is denoted $||.$

The concatenation of strings $$ and $$ is the string consisting of $$ followed by $.$ It is denoted $.$

A string $$ is a substring of the string $$ if there are strings $$ and $$ with $=.$

Project Exercises

Compute the given quantity using the strings

$a=$baab,$=$caaba,$=$bbab.

$($a$)$

$($e$)ag$

$($i$)$

$($b$)Ba$

$($f$)|a|$

$($i$)$

$($c$)$

$($g$)|||$ arol$|$

$($k$)$

$($d$)$

$($h$)||$

$(1)$

List all strings over $x=\{0,1\}$ of length $2.$

List all strings over $x=\{0,1\}$ of length $2$ or less.

List all strings over $x=\{0,1\}$ of length $3.$

List all strings over $x=\{0,1\}$ of length $3$ or less.

Find all substrings of the string babc.

Find all substrings of the string aabaabb.