1

How would i go about making a regular expression that alternates between smaller and bigger numbers for an alphabet {0,1,2,3} such as "01032312" or "230102132"

BrianO
  • 16,579
Bazoozoos
  • 45
  • Try it first with alphabet ${0,1,2}$, or if that's still puzzling, even ${0,1}$. – BrianO Oct 18 '15 at 10:39
  • Still have no clue, I've been trying this for hours. – Bazoozoos Oct 18 '15 at 13:19
  • Coming up with an NFA is not that hard (for the simpler cases I proposed, even for the one in your question)). I'm probably overlooking something but I'd say it's more difficult to find an equivalent RE. Are you supposed to use a procedure to convert from e.g. an NFA or a regular grammar to an RE? What's in your toolkit? – BrianO Oct 18 '15 at 22:15
  • @wece Quite so. And for length 3? In the NFAs I came up with, I needed states to track last symbol scanned + evenness/oddness of # of symbols scanned so far -- so, two different "just saw a 1" states, for example. Most of the states are accepting, and transitions are between "even" and "odd" states. – BrianO Oct 19 '15 at 08:14
  • @wece not entirely clear no. You can't just append 0 to 10, for example -- 100 $\notin L$. Or, sticking to "just saw 1", you can't append 1 to 21. – BrianO Oct 19 '15 at 08:25
  • @wece Ah, sorry, I started with zig not zag. But 01 is in the language, and 011 is not. – BrianO Oct 19 '15 at 08:35
  • @wece But no wonder that little confusion: the title says "alternating between bigger and smaller" which is what I was thinking; whereas the question body says "alternating between smaller and bigger". Anyway, the examples make it clear it's the latter. I'll fix the title :) – BrianO Oct 19 '15 at 08:37
  • @BrianO :D true it is confusing. You are totally right I get the part smaller to bigger and totally overlooked the bigger to smaller. Sorry. NFA looks indeed like the good solution to go with. (I remove my past comments to clarify a bit this comment section.) – wece Oct 19 '15 at 08:43
  • @wece The NFAs aren't bad, they're kinda natural. But the REs they suggest aren't very pretty, and certainly are less human-friendly. Not to worry -- I can see you're plenty sharp :) Thanks again for catching my cap/cap nonsense in the other answer. // PS I fixed the title, it'll show up soon if it hasn't already. – BrianO Oct 19 '15 at 08:49
  • @wece One last thing: I've been saying "NFAs" but really they're totally deterministic. I just didn't bother adding the non-accepting "sink state" which bum transitions go to and from which there's no escape. All other states except "start" are accepting. – BrianO Oct 19 '15 at 08:59

1 Answers1

1

As @BrianO said I think the best way to go is to build a NFA (which is not too hard) and then translate it to a regular expression.

However, if you don't know the translation from NFA to regular expression (I strongly advise you to take a look at it), or if you don't want to use it here is an attempt to directly build the regular expression.

First consider the problem for the alphabet $\{0,1\}$. The only possibility is to alternate between 0 and 1. So the regular expression is $(01)^*$.

Now consider $\{0,1,2\}$. The 2 plays a key role. First it cannot appear in odd position otherwise there are no bigger number to follow. Second, whenever a 2 is in even position there are no restriction on the next letter (apart from: it is not a 2), it is the same as the beginning of the word.

So the regular expression $((0.1)^*.0.2+1.2)^*$ matches your language:

  1. After a $0$ in odd position there can be a $1$ or a $2$
  2. After a $1$ in odd position there can only be a $2$
  3. The are no $2$ in odd position
  4. After a $2$ in even position there can be a $0$ or a $1$
  5. After a $1$ in even position there can only be a $0$
  6. The are no $0$ in even position

Lets get a look at $\{0,1,2,3\}$ now. With the same idea we get:

$$ ((((0.1)^*.0.2)+1.2)^*(03+13)+23)^* $$

wece
  • 2,732
  • Thanks for this. My FSM has 5 states including the starting state for the alphabet {0,1,2}. The states represent an odd 0, odd 1, even 1, even 2, and there are 8 transitions. Is this correct? – Bazoozoos Oct 23 '15 at 14:10