4
$\begingroup$

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to an nth power just means that 0 or 1 occurs n times, correct?

For example: the language $L = \{ 0^n \mid n ≥ 1 \} \cup \{ 1^m 0^k \mid m,k ≥ 0 \}$.

My interpretation of this represents strings with at least one zero or any number of ones followed by any number of zeroes. Strings like 001111000 and 0000110 would not be accepted. What confuses me here is that anything raised to the 0th power is 1, so I'm not sure if a string accepted by this language must have at least 1 one and 1 zero. I've included images of my state diagrams if that helps: enter image description here

Another language I am having trouble understanding is $L = \{ w ∈ \{0,1\}^* \mid w = 0x0, ∀x ∈ \{0,1\}^* \}$.

My interpretation is as follows: the * star means zero or more, and the ∀ means 'for all, for every', so this language accepts any string that starts and ends with 1 zero, with any number of ones and zeroes in between. I originally thought this was the set of strings that was just a single one or zero between 2 zeroes, so either 010 or 000. I'm still not entirely sure which one is right. I'd be so grateful for any advice. Thank you!

$\endgroup$
2
  • $\begingroup$ That last example is sloppy notation. It would be better written as $L = \{ w ∈ \{0,1\}^* \mid ∀x ∈ \{0,1\}^*, w = 0x0 \}$ (like in programming, you should introduce variables before you use them). Push back against such notational abuses. $\endgroup$ Commented Feb 15 at 17:55
  • 3
    $\begingroup$ The last language makes no sense to me, unless it is supposed to be the empty language. Should that “forall” be an “exists”? $\endgroup$ Commented Feb 16 at 5:16

3 Answers 3

8
$\begingroup$

You need to distinguish between three kinds of operations:

  • Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer multiplication.
  • Operations on strings of characters. $0^3 = 000$ when $0$ is a string of characters of length 1. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is string concatenation. (Usually, concatenation is written without any symbol at all, so the $⋅$ does not appear, but that is just a notational shorthand. You need to think of it as an operation anyway.)
  • Operations on languages (sets of strings). Operations on strings can be "lifted" to work on sets of strings. For instance, $⋅$ when applied to sets of strings is pairwise application of $⋅$ on the individual elements. Hence, $\{0\}^3 = \{0\} ⋅ \{0\} ⋅ \{0\} = \{xyz \mid x,y,z \in \{0\}\} = \{000\}$.
$\endgroup$
1
  • 5
    $\begingroup$ In particular, for any $x$, $x^0$ is an empty product, i.e. the identity element for the $⋅$ operation. The identity for integer multiplication is $1$ (since $1⋅x = x⋅1 = x$), whereas the identity for string concatenation is the empty string (often denoted by the symbol $\epsilon$). $\endgroup$ Commented Feb 15 at 16:56
6
$\begingroup$

Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^* = \bigcup\limits_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the set of finite words of length $n$ over $\Sigma$. For every two words $w,v\in \Sigma^*$, we define the concatenation $w\cdot v$ as the word $w v$. Then, once we have concatenation, we can define $w^n$, for every natural $n\geq 0$, as the word that is obtained by concatenating $w$ to itself $n$ times, in particular, the empty-word $\epsilon$ is obtained as a concatenation of length 0; that is $w^0 = \epsilon$.

So as you've seen by defining concatenation, we have defined powers of words, and this can be lifted also to languages: given two languages $L_1, L_2 \subseteq \Sigma^*$, the concatenation $L_1\cdot L_2$ is defined as the language $\{ u\cdot v: u\in L_1, v\in L_2\}$ which is the langauge of words that can be partitioned to two words, the first one is in $L_1$ and the second is in $L_2$. Now we can generalize that and for a natural $n\geq 0$ and a language $L\subseteq \Sigma^*$ define $L^n = \underbrace{L\cdot L \cdot L \cdots L}_{n \text{ times}}$; Note that we define $L^0 = \{ \epsilon\}$ as epsilon is obtained as a concatenation of length 0. We can also proceed and define $L^* = \bigcup\limits_{n\geq 0} L^n$. Note that $\Sigma^*$ is defined before the star of a language, yet it reads the same. You can think of $L^*$ as a generalization of $\Sigma^*$ for all languages $L\subseteq \Sigma^*$.

The point here is that we have powers of words, and powers of languages. Any word to the power of $0$ equals epsilon, and any language to the power of $0$ (even the empty language) equals the the language containing only the empty word. Everything boils down to the concatenation which is simply "putting two words next to each other".

There are also regular expressions that have the kleene-star operation, union, and dots in their syntax, etc. For example, $r = (0\cdot 1)^*\cdot (1\cup 2)$ is a regular expression. Not to confuse with operations on words or languages, regular expressions is another way to generate regular languages. The 1 and 0, and $*$ in the regular expression $r$ are symbols in its syntax, not words or $*$ of a language.

$\endgroup$
5
$\begingroup$

For a (usually finite) set $A$ the star denotes the free monoid on $A$ where

$$A^* = \{a_1a_2...a_k : k \geq 0 \land \forall i. a_i \in A\}$$

is the set of all finite sequences or strings of elements in $A$. So

$$\{0, 1\}^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, ...\}.$$

A string raised to the $0$th powers isn't $1$, it's $\varepsilon$. The reason for this ist that $A^*$ forms a monoid under concatination, meaning that

  • conatenation is associative: $(uv)w = u(vw)$ for $u, v, w \in A^*$
  • there's an identity element: $\varepsilon u = u \varepsilon = u$ for $u \in A^*$

Exponentiation for monoids is defined as follows, $x^0$ is the identity element and $x^{n + 1} = x(x^n)$.

$\mathbb{R}$ also forms a monoid under multiplication, and that's why for all $x \in \mathbb{R}$ holds that that $x^0 = 1$ since $1$ is the identity of $\mathbb{R}$. But the identity of the free monoid $A^*$ is $\varepsilon$, so $u^0 = \varepsilon$ for all $u \in A^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.