A dirty little ditty on Finite Automata

Some Formal Definitions

A Deterministic Finite Automata (DFA) is

  • A set \mathcal{Q} called “states”
  • A set \Sigma called “symbols”
  • A function \delta_F:\mathcal{Q}\times\Sigma \to \mathcal{Q}
  • A designated state q_0\in\mathcal{Q} called the start point
  • A subset F\subseteq\mathcal{Q} called the “accepting states”.

The DFA is then often referred to as the ordered quintuple A=(\mathcal{Q},\Sigma,\delta_F,q_0,F).

Defining how strings act on DFAs.

Given a DFA, A=(\mathcal{Q}, \Sigma, \delta, q_0, F), a state q_i\in\mathcal{Q}, and a string w\in\Sigma^*, we can define \delta(q_i,w) like so:

  • If w only has one symbol, we can consider w to be the symbol and define \delta(q_i,w) to be the same as if we considered w as the symbol.
  • If w=xv, where x\in\Sigma and v\in\Sigma^*, then \delta(q_i, w)=\delta(\delta(q_i,x),v).

And in this way, we have defined how DFAs can interpret strings of symbols rather than just single symbols.

The language of a DFA

Given a DFA, A=(\mathcal{Q}, \Sigma, \delta, q_0, F), we can define “the language of A“, denoted L(A), as \{w\in\Sigma^*|\delta(q_0,w)\in F\}.

Some Examples, Maybe?

Example 1:

Let’s construct a DFA that accepts only strings beginning with a 1 that, when interpreted as binary numbers, are multiples of 5. So some examples of strings that would be in L(A) are 101, 1010, 1111

Some More Formal Definitions

A Nondeterministic Finite Automata (NFA) is

  • A set \mathcal{Q} called “states”
  • A set \Sigma called “symbols”
  • A function \delta_N:\mathcal{Q}\times\Sigma \to \mathcal{P}\left(\mathcal{Q}\right)
  • A designated state q_0\in\mathcal{Q} called the start point
  • A subset F\subseteq\mathcal{Q} called the “accepting states”.

The NFA is then often referred to as the ordered quintuple A=(\mathcal{Q},\Sigma,\delta_N,q_0,F).

Defining how strings act on NFAs.

Given an NFA, N=(\mathcal{Q}, \Sigma, \delta, q_0, F), a collection of states \mathcal{S}\subseteq\mathcal{Q}, and a string w\in\Sigma^*, we can define \delta(\mathcal{S},w) like so:

  • If w only has one symbol, then we can consider w to be the symbol and define \delta(\mathcal{S},w):=\bigcup\limits_{s\in\mathcal{S}}\delta(s,w).
  • If w=xv, where x\in\Sigma and v\in\Sigma^*, then \delta(\mathcal{S}, w)=\bigcup\limits_{s\in\mathcal{S}}\delta(\delta(s,x),v).

And in this way, we have defined how NFAs can interpret strings of symbols rather than just single symbols.

Maybe in another post, we’ll get past the definitions! :-/

Advertisements
A dirty little ditty on Finite Automata

What’s in a language?

What is a Formal Language?

The Rigorous definition:

Let \Sigma be an alphabet and let \Sigma^k be the set of all strings of length k over that alphabet. Then, we define \Sigma^* to be \bigcup\limits_{k\in\mathbb{N}}\Sigma^k (the union of ∑k over all natural numbers k). If L\subseteq\Sigma^*, we call L a language.

The Intuition Behind the Definition

Consider an alphabet (some finite set of characters), for example we can consider the letters of the English language, the ASCII symbols, the symbols \{0, 1\} (otherwise known as binary), or the symbols \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, \times , =\}. We can then construct the infinite list of all the different ways we can arrange those characters (e.g. 1001011 or 0011011011, etc. if we’re using binary). We call these arrangements “strings”. Once we have all that machinery built up, a language is just some subset of that infinite collection of strings. The language may itself be infinite.

Some Examples

  • The alphabet: \Sigma=\{0, 1\}
    The language: \{x\in\Sigma|x \text{ is prime}\} (all prime numbers in binary)
    Some strings from the language: 10, 11, 101...
  • The alphabet: ASCII characters
    The language: All syntactically correct Clojure programs (the source code)
  • The alphabet: All Clojure functions, operators, etc, and list \{x, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0\}
    The language: All syntactically correct Clojure programs (the source code)

You see that we need to have an alphabet before we can have a Formal Language. Also, different alphabets may result in equivalent languages — by equivalent, we mean that both languages contain the same strings.

What are we getting at?

Well, there are two ways to look at this. On the first hand, linguists would like to study language in its abstract essence. For this, Formal Languages may come in handy (if endowed with a Grammar and possibly more). That is not the reason I will be studying Formal Languages. I’m learning about formal languages to find their applications to computing.

Apparently, with the help of a little Mathematical thinking, we can assign semantics to the strings in a language and somehow correlate them with real world problems — such as computability, the P=nP problem, cryptography, and more!

What’s in a language?