retagged by
20,096 views
57 votes
57 votes
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ denote composition on functions. For a string $x=x_1 x_2 \dots x_n \in \Sigma^n, n \geq 0$, let $\pi(x)=x_1 \circ x_2 \circ \dots \circ x_n$. Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
retagged by

5 Answers

Best answer
51 votes
51 votes

Answer $-120$

I am rewriting question in (hopefully) simple way-

There are $5! = 120$ bijection functions possible. let $f_1, f_2, \dots f_{120}$ be functions. we can represent every function $f_i$ with some string $x_i$.

Now we take the composition of functions $f_i$ and $f_j$ then the corresponding string is $x_ix_j$ (Composition of two functions in function space is the concatenation of corresponding strings in string space).

eg: Composite function $f_i\circ f_j\circ f_k$ has representation $x_ix_jx_k$ and so on.

A function can have multiple string representations, suppose $f_i = f_j\circ f_k$ then $f_i$ has $x_i$ and $x_jx_k$ both representations. And further, suppose $f_i = f_p\circ f_q\circ f_r$ then $x_px_qx_r$ also maps to $f_i$.

There is a given function called $\pi$ which does the same job. i.e.  $\pi$ maps a string to the corresponding function. (It is obvious to see that $\pi$ is many to one function.)

We need to construct a DFA, which accepts a set of all strings whose function representation behaves like Identity function.

$x_1x_2\dots x_n$ is accepted If and Only If  $f_1\circ f_2\circ\dots\circ f_n$ is identity function.

In other words, Design a DFA for $L=\pi^{-1}(id)$.


Solution:

First interesting and important point to note is, $\pi(\epsilon) = id$.

Quick check for above statement: Suppose it is not the case and  $\pi(\epsilon)$ is some nonidentity function $f$. Then consider a string $x_1x_2x_3$ which maps to a function $f_{123}$ (where $f_{123} = f_1\circ f_2\circ f_3$) i.e. $\pi(x_1x_2x_3) = f_1\circ f_2\circ f_3 = f_{123}$ . Now we can always append epsilon to a string   $x_1x_2x_3 = x_1x_2x_3\epsilon$.  $\pi( x_1x_2x_3\epsilon) = f_1\circ f_2\circ f_3\circ f= f_{123}\circ f \ne f_{123}$.

This concludes that $\pi(\epsilon) = id$, therefore, $\epsilon$ must be accepted by our DFA.

Now we can construct a DFA over alphabet $\Sigma = \{x_1, x_2, \ldots, x_{120}\}$ which has $120$ states corresponding to $120$ functions. 

Initial state and final state will be the same which corresponds to the Identity function.

For any string $x_ix_j$, DFA will move to state corresponding to function $f_i\circ f_j$ and let $f_k = f_i\circ f_j$ . Therefore on string  $x_ix_j$, DFA will be in state corresponding to function $f_k$. 

(I have written $f_k = f_i\circ f_j$ , where $f_k$ is one of the function in $f_1, f_2, \ldots, f_{120}$, because this set of bijective functions $ \{f_1, f_2, \dots, f_{120} \}$ is closed under composition ).

Formally, we have DFA $M=(\Sigma,Q,q_0,\delta,F)$ for  $L=\pi^{-1}(id)$.

where, $\Sigma = \{x_1, x_2, \ldots, x_{120}\}$

$Q =\{ f_1, f_2, \dots, f_{120} \}$ (let name of $i^{th}$ state is $f_i$)

$q_0$ = $f_{id}$ ( $f_{id}$ is identity function)

$\mathbf{\delta(f_i,a)=f_i\circ\pi(a)}$,  $\forall a \in \Sigma$

$F= \{f_{id}\}$

edited by
23 votes
23 votes

Number of bijective functions from $\{1,\dots,5\}$ to $\{1,\dots,5\} =5!=120.$

Now, our alphabet set $\Sigma$ is having $120$ elements -- say for example first $120$ ASCII characters representing each of these $120$ distinct functions.

Out of these $120$ bijective functions there is exactly one identity function - say it is denoted by the ASCII character $I$ in our example alphabet set.

Now, say we make an $NFA$ with $120$ states such that from the initial state we move to state represented by function $f_i$ for the symbol corresponding to $f_i$. i.e., in our ASCII set, for symbol $'A'$ we move to state $A$, for symbol $'B'$ we move to state $B$ etc. and for symbol $I$ we say in same state. In detail,

  • For first symbol of input string, we say in start state if the symbol is $I$
  • For any other $119$ symbols possible we move to the corresponding state for that symbol
  • Now say for symbol $A$ we moved to state $A$ and the second symbol is $K$ where the function represented by $K$ is the inverse of the function represented by $A$. In this case we move back to the start state 
  • We can assume each of the state represents a permutation of $1,2,\dots 5$ 
  • From any state, represented by a permutation of $1,2,\dots 5$ say $s$, for the next symbol $b$ we move to the state given by $f_b$ applied on $s.$
  • When the string ends, if we happens to be in start state, or equivalently we simulated an Identity function, then we accept. Else reject. 

If we see the above $NFA$ is actually a $DFA$ and we cannot minimize it. So, we will need minimum $120$ states to recognize $L.$

PS: The mapping of the $120$ functions to the corresponding symbols is assumed in the question

11 votes
11 votes

NPTEL REFERENCE: Watch from 11:59

So you will learn that composition of function is also a bijection.

Now, in our question we are asked about S5 in general, 

now, we will have 120 different elements in our group s5

s5 = {f1,f2,f3,f4,…,f120}

I am proud to say that this question I understood from NPTEL and this is a direct question from them, Please watch the video and try to solve this question, this question demands group theory knowledge in advanced. 

Some people say this question is difficult, but once you see this video, you wont see it as it is difficult

Now the problem boils down to why 120 states, as there are 120 bijections possible, f1 as mentioned in the picture, will be the identity element of this group, you can yourself verify

f1 op f1 = f1

f2 op f1 = f2

f120 op f1 = f120

also this group is closed, 

if you are interested, you can find generators of this group as mentioned in the video, for S3 as it was simple.

 

I would recommend everyone to watch this video

reshown by
2 votes
2 votes

I propose below answer.

Answer = 11


What is a bijection from X = {1..5} to Y = {1..5}? 

Let's first look at bijections on say (1,2) to (1,2). These are two bijection functions: f1 = {(1,1),(2,2)} and f2 = {(1,2),(2,1)} and Σ = {f1,f2}

Similarly lets look at bijections on say (1,2,3) to (1,2,3). There are six functions:

f1 11,22,33
f2 11,23,32
f3 12,21,33
f4 12,23,31
f5 13,31,22
f6 13,32,21

Here Σ = {f1,f2,f3,f4,f5,f6}

These can be extended to any number of symbols. Bijections from X = {1..n} to Y = {1..n} are n! in number.

So in out case of n=5,

Σ = {f1,f2,f3...f120}

where each f is a set of mappings from {1..5} to {1..5}

 


What is Σ² ?

It's the cartesian product of sigma and sigma. This means we go from domain for first Σ to range of first sigma, which is the domain of second Σ to the range of the second Σ.

Because domain and range are the same - {1..5}, we note that Σ² is still a set of functions from x ∈ X = {1..5} to some y ∈ Y = {1..5}


What is Σ^n ?

We can extend the above argument for Σ²  to any number of compositions. 

Because domain and range are still the same - {1..5}, we note that Σ^n is still a composite function from x ∈ {1..5} to some y ∈ {1..5} (with some intermediary domain and ranges (or intermediate states) corresponding to the composing functions)

Questions remaining:

1) What is a string

2) What is the final mapping we are looking for?


What is a string? OR what is actually happening?

Say we understand the above function, how does it relate to a string? The string maps the exact domain and range of the various composing functions.

For instance lets take Σ².

Consider the sample space of Σ² = S

S = {(1,1)->(1,1), (1,1)->(1,2), (1,1)->(1,3), (1,1)->(1,4), (1,1)->(1,5), (1,2)->(2,1), (1,2)->(2,2), (1,2)->(2,3), (1,2)->(2,4), (1,2)->(2,5),(1,3)->(3,1),...(1,5)->(5,1),(1,5)->(5,2),(1,5)->(5,3),(1,5)->(5,4),(1,5)->(5,5)} which can also be written as

S = {(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,2,1),(1,2,2),(1,2,3),(1,2,4),(1,2,5),(1,3,1),...(5,5,1),(5,5,2),(5,5,3),(5,5,4),(5,5,5)} respectively

with corresponding strings 111,112,113,114,115,121,122,123,124,125....551,552,553,554,555

Now Σ² corresponds to some subset of all possible functions each of which contain certain number of elements from this sample space. Therefore we can say Σ² is a function that contains some elements from this sample space S.

 

Moving from functions to finite automata, any DFA we construct is seeing some strings and making transition between states based on string it sees. These strings are composed of the symbols {1..5}. The language accepted by the DFA represents the function.

 


What is the final mapping we are looking for? OR What is id or identity function?

The identity is some function from X to Y such that x=y where x ∈ X = {1..5} and y ∈ Y = {1..5}.

This means an identity function is eventually composed by any number of intermediary functions such that each element x in the domain maps to the same element y in the range of the aggregate (composed) function.

 

Say S is a string that represents the above function type. This means that through any number of transitions in between, it has to go from some the initial state x ∈ {1..5} to final state y ∈ {1..5} such that x=y

In other words. S = xabcdef....y

Where:

1) Each of x,a,b,c,d,e,f ...y  ∈ {1..5}

2) x = y


What does this mean?

We are looking for strings on {1..5} of any length which start and end with same symbol.


Now, stated this way construction of DFA is much easier.

We have:

one state for start state - call this S

One state for each of the initial transitions call these states A, B, C, D and E

One state for each of the variations - call these A', B', C', D' and E'

So 11 states

 

reshown by
Answer:

Related questions

40 votes
40 votes
4 answers
2
18 votes
18 votes
4 answers
3