CODEWITHSUNDEEP
finite-automataautomata
Lobs001
Lobs001

Reputation: 365

Definition of a language in Automata Theory

I'm currently taking a class in Automata Theory, and while still at Finite Automata, I do find it both interesting and challenging.

We are using 'Introduction to Automata Theory...' by Hopcroft and it talks about a DFA in the notation:

A = (Q,Σ, δ, q 0,F)

This is fine, but then, our professor has given us some exercises (probably not in the book), I'm asked to create a machine with the

LANGUAGE

This kind of confuses me, since the book doesn't describe exactly how to define a language. I asked the professor but he didn't give a good explanation, if a proper explanation at all (I'm not sure if he fully understands it himself to be honest).

Let's take L = 010 for example. What does this mean exactly? Is the only acceptable state in this language '010'?

Also, how does L = {0,1} differ from Σ = {0,1}?

Also, why isn't the definition of a languge included in the DFA "five-tuple" notation A = (Q,Σ, δ, q 0,F)?

I appreciate any help I can get on this subject. Thanks!

Upvotes: 0

Views: 5264

Answers (1)

Patrick87
Patrick87

Reputation: 28312

L = 010

This is sort of an abuse of notation and most likely means L = {010}. That is, L is the language consisting only of the word 010. A DFA for it has five states: q(-), q(0), q(01), q(010), and q(r). q(-) is the initial state, q(r) is a dead state, and q(010) is accepting. The transitions are such that the desired state is built as you transition along and any incorrect input leads to q(r).

L = {1,0}

This is the language with just two terms, 0 and 1. A DFA for it has three states: q(-), q(a) and q(r). q(-) is the initial state, q(a) is accepting and q(r) is dead. q(-) goes to q(a) on 0 or 1 and all other required transitions go to q(r).

L = {1,0}*

This is the language of all binary strings. It has one state, q(-), which is accepting and transitions to itself on either 0 or 1.

L = {0^n | where n is >= 0)

This is the language of all strings of 0s. It has two states, q(-) and q(r). q(-) is initial and accepting and loops to itself on 0; all other required transitions go to q(r), a dead state.

Also, how does L = {0,1} differ from Σ = {0,1}?

Σ refers to an alphabet and is a non-empty finite set of symbols, in this case, 0 and 1. It is important that the symbols of an alphabet be considered atomic in the sense that any string of such symbols can be unambiguously interpreted in only one sense.

L refers to a language of strings over some alphabet, in this case, Σ from above. Strings are sequences (we typically limit our consideration to finite sequences) of symbols from an alphabet. Languages are sets of such sequences. L = {0, 1} is the set of length-one sequences (0) and (1) over the alphabet {0, 1}. 0 can refer to either the symbol or the length-one sequence consisting of that symbol, depending on context. Whether you consider them "the same" or not is a philosophical question but from a programmer's perspective it is best to think of them as distinct.

Also, why isn't the definition of a languge included in the DFA "five-tuple" notation A = (Q,Σ, δ, q 0,F)?

Languages are sets of strings. DFAs are theoretical machines which are capable of processing strings of input. The relation between DFAs and (regular) languages is that the latter can be defined as sets of strings of input accepted by the former. Other equivalent definitions can be given for (regular) languages, e.g., the sets of strings matched by regular expressions.

Upvotes: 2

Related Questions