Ok first of all I'm not sure if this is the forums for help on theory type questions but here it is.

In 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:

 

 

{ a^ib^jc^k: i + j >= 5, k – j >= 3 }

 

 

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

 

 

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

 

 

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

 

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

I'm a bit out of my depth here, but I think you may be confusing a regular language with a regular expression engine (which is really what this forum is all about).

In fact, "a*b*" is a regular expression in the sense used in this forum in that it will match all of the following strings

aaaabbbb
aaaaaabbbbbb
aaaaa
bbbbb
    <= that's a blank string

The regex engine will try to match zero or more 'a' and stop when the next character it comes to is not an 'a'. It will then try to match zero or more 'b's and stop when the next character is not a 'b'. This means that it will also match:

gfde

by matching the 'null' substring right at the beginning.

Your other examples may be definitions of a regular language which may be implementable in a LL(1) or some other form of parser. However, they are not recognisable as 'regular expression' patterns that we normally talk about here.

Susan