Math Is Fun Forum

Kenshinofkin

Member

Registered: 2008-07-08

Posts: 6

Regexp help

I my class we went over nonregular languages a little bit but not much at all. I understand that a*b* is not a regexp because there can be an infinite number of a's or b's but all of the following seem to me like they are regexps:

How can I fine if they are a regexp or not. They all seem to be.

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Regexp help

Kenshin wrote this math but it didn't show up.
{ a^ib^jc^k: i + j >= 5, k – j >= 3 }

{ a^nba^n: n >= 0 }

{ a^nb^m: n >= m }

{ all strings, w : n_a(w) mod 2 > n_b(w) mod 2 } (Note: n_a(w) is the number of a’s in the string w)

---

igloo myrtilles fourmis

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Regexp help

It's been a few years since I've done anything with formal languages, but what I think you're looking for is a Type-3 grammar on the Chomsky hierarchy (thank goodness for Wikipedia, I never would have remembered something that detailed).  This means that the language can be generated with a right regular grammar, which means that it can be completely generated with rules of the following type:

A -> b
A -> cD
A -> empty string

For example, let's say that all expressions start with S.  Here's the grammar (or language, I'm unsure of the proper terminology) for the expression a*b*:

S -> aS
S -> bA
S -> empty string
A -> bA
A -> empty string

You can see that by starting with S and following the above rules that we can generate any expression in a*b*.  As another example, let's try to make a list of rules for a(a|b)*:

S -> aA
A -> aA
A -> bA
A -> empty string

Now, with that in mind let's take a look at your examples.  The easiest one would be the second expression: a^n b a^n, n >= 0.  How can we come up with a list of rules for this expression?  Let's start with the beginning a's:

S -> aS

Easy enough.  It's also trivial to add a single b in the middle:

S -> bA

Now we get to the tough part.  How do we make a rule so that we add exactly as many a's as before?  You can see it's plainly impossible, since we have no way of keeping track of how many a's we added at first.  Therefore, this cannot be a regular expression.  This is easily proven for the other expressions as well.  The problem is that they all require you to keep track of how many letter's you've already written, which is not possible for regular expressions.

---

Wrap it in bacon