0
$\begingroup$

the question is as follows, further the notation used are standard as used in theory of computation $$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$

Beware 'K' is not a fixed integer its a set of natural number , so 2k means all natural nunbers divisible by 2 and so on for 3k , 4k... .I think the above language is irregular or its finite automata can't be formed. Firstly the above question in basic language can be thought of as modulus of difference of number of $a$ and number of $b$ is divisible by $2$ or is even , similar to this reasoning we can extend this to more general like $3k$, $4k$, $5k$,... and so on. Secondly we know that any condition which have comprise the difference between the symbols would have infinite possible comparison between symbols, like an equation of $n(a) - n(b) =0/1/2/3...$ needs infinite states of finite automata which makes them irregular.

But here with the use of modulus it seems no different as here also we will need many comparison between symbols.

Thirdly its more of a general question like when define regularity of language $L$ over condition like, $n(a) - n(b)\bmod 3 =0$, we say the all strings can be classified as having either remainder $0$,$1$,$2$ which by using Myhill-Nerode theorem proves the language regular. But why cant we use the same analogy over the relation like $n(a) -n(b)=2$ saying the all the strings would either have a difference $2$ or not. Further if you could answer the regularity of $n(a)- n(b) = 2k$, also how does taking modulus effect its regularity and how does it makes the states of finite automata finite which before applying modulus were infinite if you could a graphical representation would be appreciated.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ "$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}$", you said. Do you mean $L_k = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}$ for some fixed non-negative integer $k$, or $L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| \text { is even}\}$? Apparently, people are answering your question according to either one of these interpretations. $\endgroup$
    – John L.
    Commented Sep 30, 2018 at 7:29
  • $\begingroup$ @Apass.Jack yeah the language described is just a single case of a generalisation but it answers only one aspect my whole problem which have a many small yet important aspect connected to the language L but here the have just made an automata of language and that it @ david had said for generalisation but iam awaitng his further response $\endgroup$
    – rballiwal
    Commented Sep 30, 2018 at 11:35
  • 2
    $\begingroup$ Sorry, which one do you mean? I asked a question of two choices. But you answered with yes. Once again, do you mean $L_k$ for a fixed $k$ or do you mean the difference is even? Or do you think those two choices are the same (to me, those two choices are very different)? $\endgroup$
    – John L.
    Commented Sep 30, 2018 at 15:08
  • $\begingroup$ @Apass.Jack i request you to read question once again and i think you will find that i have asked more than two thing of which some being like , whether is the difference ( N(a) -N(b) )is even(or divisible by 2) ,but i have asked the same in more general form like is the difference( N(b) -N(b) ) is divisible by 3 to which i have written an equation of form N(a) -N(b) = 3k , where 3k being set of natural numbers. i thought that you will understand but my bad you did not . so can you answer now that whether for ( N(a)-N(b) ) =3k (where k is set of natural number ) we can form a finite automata $\endgroup$
    – rballiwal
    Commented Oct 1, 2018 at 6:15
  • $\begingroup$ i will upvote it if found good $\endgroup$
    – rballiwal
    Commented Oct 1, 2018 at 6:58

2 Answers 2

Reset to default
3
$\begingroup$

You seem to be assuming that, to determine whether $n(a)-n(b)$ is a multiple of $m$ requires us to computer $n(a)$ and $n(b)$, subtract them, and then calculate the remainder. You're correct that a finite automaton can't do that, but it's not the only way.

The first thing to note is that you can computer $n(a)-n(b)$ directly. Initially, you've seen no $a$s or $b$s so the difference is zero. Each time you see an $a$, the difference increases by one; each time you see a $b$, the difference decreases by one. OK, that's a bit smarter but it still requires us to compute the value $n(a)-n(b)$, which could still be arbitrarily big, so still can't be done with a finite automaton.

The second thing to note is that, because of the way that modular arithmetic works, $$(x-y)\bmod m = ((x\bmod m) - (y\bmod m)) \bmod m\,.$$ In other words, you can do everything modulo $m$. Each time you read an $a$, the difference increases by one modulo $m$. and each time you read a $b$, it decreases by one modulo $m$.

This means that you can recognize the language with an automaton with $m$ states: one for each value of $n(a)-n(b)\bmod m$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ ok i have no problem with modulo but , by your reasoning i assume that we can formulate an automata of n(a) -n(b) = 2k, 3k,.. even for the conditions like |n(a)- n(b)| = even, odd, 3k,2k,. (remember i have used modulus function that is different from modulo function) with modulus the reason being that the difference between a and b being divisible by 2 without any order in occurrence of a and b. but when we say , n(a)- n(b) =2k we say that the order of occurence of a and b matters . is that right? , also we can say that (n(a)-n(b)) mod 2 =0, have same language as (n(a) -n(b) ) mod 2 =0 ? $\endgroup$
    – rballiwal
    Commented Sep 29, 2018 at 15:13
  • $\begingroup$ Oh, sorry, I missed the modulus. I don't have time to look at this now but I'll try to see later if it makes any difference. $\endgroup$
    – David Richerby
    Commented Sep 29, 2018 at 15:36
  • $\begingroup$ one more thing that we cannot form finite automata for n(a) - n(b) = 2k, 3k,4k...and so on $\endgroup$
    – rballiwal
    Commented Sep 29, 2018 at 16:07
  • $\begingroup$ i find your answer incorrect if you are saying that for N(a)-N(b) = 2k, 3k... we can not form an automata. beacuse we can $\endgroup$
    – rballiwal
    Commented Oct 2, 2018 at 2:45
2
$\begingroup$

For the given language $|n(a) - n(b)|$ will be even only if either $n(a)$ and $n(b)$ are both odd or both even.

In any case the total no. of symbols should be even.

So we have two states: q0 : where the total no. of symbols is even (accepted state)

q1: where the total no. of symbols is odd.

Fig1. for |n(a) - n(b)| = 2k

In general: $|n(a) - n(b)| = mk\ $ for some $k\ge0$ if and only if $n(a)\mod(m) = n(b)\mod(m),$ i.e. both number of 'a's and number of 'b's have same remainder when divided by $m$.

now difference between $n(a)\mod(m)$ and $n(b)\mod(m)$ can be $0, 1, 2, 3, 4, \cdots, m-1$.

So there will be $m$ states, each representing the difference : $n(a) - n(b) \mod(m)$. The state diagram will be something like: Fig2. |n(a) - n(b)| = mk

Improve this answer
$\endgroup$
10
  • $\begingroup$ if you could then , could you tell me that whether there exists an automata for n(a) -n(b) = 2k,3k,4k... $\endgroup$
    – rballiwal
    Commented Sep 29, 2018 at 18:33
  • $\begingroup$ also bear that here the equation is simplified but by your logic can we say that there exist a finite automata for |n(a) -n(b) |= 2k,3k,4k... ?, which inturn implies some relation to be occurred with n(a)-n(b) =2k,3k,4k.... $\endgroup$
    – rballiwal
    Commented Sep 29, 2018 at 18:41
  • $\begingroup$ @rajendra I understand a finite automata as a tool, like a blank piece of paper, on which you can note down one quantity at a time. Something like a programmable register that can store some value, but only one value. In the expression with modulus i need just the difference,, based on that I can decide whether a string matches. In case without modulus, i need to keep track of both a's and b's and that the difference is how far from multiple of k. $\endgroup$
    – aknautiyal
    Commented Sep 29, 2018 at 19:00
  • $\begingroup$ so that means N(a) -N(b) = 2k ,3k ...are not regular and there automata cant be formed ? $\endgroup$
    – rballiwal
    Commented Sep 30, 2018 at 11:43
  • $\begingroup$ @rajendra Iam a little confused here. when we say anything say "x" is a multiple of m and we write x = mk, does it not imply k is a whole number? If it does then, we need to have |n(a) -n(b)|on the left hand side. $\endgroup$
    – aknautiyal
    Commented Sep 30, 2018 at 13:23

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.