GATE CSE 2019 | Question: 48

Question

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 _______

Comments

Please share NPTEL link.

---

Please share the NPTEL video link if someone has it. Thanks!

---

120 states there…… typed 121 as an ans by considering 120 strings in hurry :/

Answer 1

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}\}$

Comments

120 can be written like this = $2^{3} * 3 * 5$

 = 11 states.

---

initial state is identity function. so there will be only 120 states.

---

^

Yeah thnks I edited :)

---

Could you please elaborate what you meant by ' we can further minimize the DFA using initial state corresponding to identity function which is also final state' ?

---

So the final answer is 120 not 121..  right?

---

The dfa should not accept epsilon. If u keep identity function as initial and final state then dfa acepts epsilon. So one more state must be added to the dfa. So answer should be 121. Please let me know if I am wrong

---

^ I added explanation in answer.

---

Well, my intention is not to complicate the question but to introduce you to one concept about regular languages.

(There is absolutely no need to know this concept for GATE purpose but I am writing in case if one is willing to know and can afford 10 mins to read out.)

Generally, we give a DFA or regular grammar to represent regular language, but we can also give a (finite) monoid to recognize the regular language.

Definition: A (homo)morphism from a monoid $(M, \circ_M,1_M)$ to a monoid $(N, \circ_N,1_N)$ is a function $h : M \rightarrow N $ such that $h(x\circ_My) = h(x)\circ_Nh(y)$ and $h(1_M) = 1_N$ (Identity element of first monoid maps to identity element of second monoid).

We have one famous monoid here (also called free monoid): $(\Sigma^*,.,\in)$ where "$.$" is concatenation operation. Let $\Sigma = \{a,b\}$.

Now if we want to prove that some language $L\subseteq \Sigma^*$ is regular then we can regonise the same language using a finite monoid M s.t. for $h : \Sigma^* \rightarrow M$, $L=h^{-1}(X)$ where $X$ is subset of $M$.

L="Set of all odd length string",  Below is monoid that recognizes L.

$(\{0,1\}, \bigoplus_2 , 0)$ where $a\bigoplus_2 b = (a+b)mod2$

According to definition of morphism, identity element of 1st monoid maps to identity element of second, i.e. $h(\in) = 0$. And once we define what $h(a)$ and  $h(b)$ are then we can map any other string using rule $h(x\circ_My) = h(x)\circ_Nh(y)$.

 $h(a)$ and  $h(b)$ depends on language in hand, if we define $h(a)=1$  and $h(b)=1$, it would work for given languange L. We can see that all odd length strings will map to 1 and hence  $L=h^{-1}(1)$.

Consider a odd length string aab, $h(aab) = h(a)\bigoplus_2 h(a)\bigoplus_2 h(b) = 1\bigoplus_2 1\bigoplus_2 1 = 1$.

similarly, $h(\text{any odd string}) = 1$. Hence $\text{All odd strings} = h^{-1}(1)$.

Consider one more language L = "Number of a's should be odd".

Same monoid will work with morphism $h(a)=1,  h(b)=0$. then  $\text{All strings with odd a's} = h^{-1}(1)$.

Once we have finite monoid for a regular language then we can always have DFA using transition rule

$\delta(m,a)=m\circ(a)$ for $a \in \Sigma$, $m \in M$ and  $h : \Sigma^* \rightarrow M$ (each element of $M$ is one state in DFA).

--------------

In above question we are already given monoid $M =\{f_1, f_2, \dots f_{120}\}$ and morphism $\pi$, all we need to tell is number of states in DFA, which is nothing but number of elements in $M$.

---

how do we know, it is minimum number of states for DFA?

---

any reason for assuming the alphabet as the set of functions on the symbols {1,2,3,4,5}?

---

https://cs.stackexchange.com/questions/104349/language-of-all-sequences-of-permutations-whose-product-is-the-identity

---

Very nice Sachin bro. I have been googling for application of elements (like fields, vector spaces, groups, rings, polynomial rings) of modern algebra especially in computer science. Now I've got an example for moniod along with homomorphism in monoid. These are usually not taught in our course. Thank you so much for posting this. May I know where you got these concepts from. Pls mail me [email protected].

---

Why can be simply said:

The number of bijections are the answer to this question.

$\mathbf{5\times4\times3\times2\times1 = 120}$

---

@`JEET because the question does not ask for the number of bijections. 120 just happens to be the answer because the NFA is a DFA and non-minimizable.

---

Can you tell how you get to the point that function here can have many representations?

---

I believe that $\pi(e)$ will be undefined, and there would be a dead state making a total of 242 states.

---

@Deepak Poonia

any video solution for above ???

Answer 2

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

Comments

@Arjun sir please can you make the NFA then it will be more clear.

---

it's not possible to draw it

Answer 3

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

Comments

Helpful👍

---

Could you link the video here please?

Answer 4

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