2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### Proving Equivalence of Two Regular Expressions

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...
• 269k
Accepted

### What is the correct way to draw NFA of RE (a|b|c)?

There is no unique way of converting a regex into NFA. That is, for any regular language $L$ there exist multiple (even, infinite) number of NFAs that accept the language $L$. The solution of your ...
• 20.3k
Accepted

### I have found an example where regular expression is not closed under concatenation. Where am I wrong?

If $n$ is fixed then $a^n$ is just a single word and so is $a^nb^n$. If by $a^n$ you mean the language $\{a^n \mid n \ge 0\}$ (whose corresponding regular expression is $a^*$) then the problem is that ...
• 22.7k

### Length of a regular expression

I assume, you want to define the length of a regular expression such that you can make statements like: The Thompson construction creates an NFA from a regular expression with a number of states that ...
• 1,439

### Length of a regular expression

There are two conventions I know of. One is defining the size of a regular expression as the size of the binary tree representing the expression. As such, the size of the expression is the total ...
• 7,154

### Regular Expressions - What is difference between a+ and a⁺

Usually that is a matter of taste. If I am nathematically motivated then I write $a^*$ like some single argument postfix operations in mathematics. If I keep close to applications, I would type $a*$ ...
• 27.2k

### Which languages do Perl-compatible regular expressions recognize?

OP already linked an awesome blog post. I did some more research on it, and found the following pieces of information: Wikipedia article on Context-sensitive grammar mentions that right-context-...
• 356
Accepted

### An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)

The empty word $\epsilon$ isn't an integer. Integers are $0, 1, 2, 3, \dots, 10, 11, \dots$ Clearly none of them have $0$ letters when you write them, and hence they are not $\epsilon$. Hence, you ...
• 10.7k
Accepted

### Proving $(a + ab)^*a = a(a + ba)^*$

This is an instance of the identity $(xy)^*x = x(yx)^*$ with $x = a$ and $y = 1 + b$: $$(a + ab)^* a = (a(1+b))^*a = a((1+b)a)^* = a(a +ba)^*$$
• 5,925

• 10.7k

### Regular expression for all a* except aa?

Hint: A word consisting of $n \neq 2$ many $a$s either consists of zero $a$s, or of a single $a$, or of at least three many $a$s.
• 269k

### If L is regular so is the language of compressed doubles

Let $h\colon \Sigma \to \Sigma^*$ be the homomorphism given by $h(\sigma) = \sigma\sigma$. Then $L’ = h^{-1}(L)$. Now use the well-known fact that regular languages are closed under inverse ...
• 269k
Accepted

### Can a non-regular language have a regular grammar?

A regular grammar generates a regular language – the existence of a regular grammar for the language of palindromes would imply the language to be regular. However, it isn't, hence a regular grammar ...
• 966

### Can any language be expressed by regular expression?

Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the ...
• 966

### How do I find the regular expression for- All binary numbers greater than 110011

If a number is more than 6 bits long (not counting leading zeroes) then it is certainly larger than your number. Otherwise, it is one of finitely many numbers, preceded by an arbitrary number of ...
• 269k

### Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*

Hint: words in $\{ww\mid w\in\{a,b\}^*\}$ have even length.
• 7,154
Your claim is true, so there is no counterexample. $\emptyset$ is a regular language and is a subset of every (non-regular) language.