Search code examples
regexregular-language

Regular expression. Regular or Irregular?

I just want to get a second opionion on these expression and whether they are irregular or regular.

{0^n 1^m | n >= m >=0} REGULAR

{0^n 1^m | n,m >=0}* REGULAR

{0^n 0^n | n>=0} IRREGULAR

can anyone confirm that this is true?

Solution

  • {0^n 1^m | n >= m >=0} Since an FSM cannot keep track of what n was in order to ensure n>=m, an FSM cannot represent the expression.

    {0^n 1^m | n,m >=0}* -- an FSM can seem to represent this but there are problems. Unlike the first problem, n and m are unrelated to one another so no FSM creation issues. The problem is that n and m must remain the same for multiple passes through the machine. Again, since there's no memory, this isn't possible.

    {0^n 0^n | n>=0} -- this is simple with an FSM as well. It looks much like the 2nd problem's FSM. The RE is (00)*