2022 Developer Survey is open! Take survey.
31 votes
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$ ...
user avatar
22 votes
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 ...
user avatar
  • 20.3k
12 votes
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 ...
user avatar
  • 22.7k
7 votes

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 ...
user avatar
  • 1,439
7 votes

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 ...
user avatar
  • 7,154
5 votes

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*$ ...
user avatar
  • 27.2k
5 votes

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-...
user avatar
  • 356
5 votes
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 ...
user avatar
  • 10.7k
4 votes
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)^* $$
user avatar
  • 5,925
4 votes

Every non-regular language has a subset which is a regular language?

In order to make the question more interesting, let us ask for the regular subset to be infinite. Here is an example of an infinite language with no infinite regular subset: $$ \{ a^{n^2} : n \geq 0 \}...
user avatar
4 votes

What is the language of this simple DFA with 4 states?

Description in plain English A binary string is accepted by the DFA iff its longest suffix that looks like $1010\cdots1$ has an odd number of $0$s. In other words, A binary string is accepted by the ...
user avatar
  • 33.1k
4 votes

Proving Equivalence of Two Regular Expressions

If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's ...
user avatar
  • 143
3 votes
Accepted

Minimal state DFAs for a regular expression of length $n$

According to Theorem 11 of Gruber and Holzer, From Finite Automata to Regular Expressions and Back – A Summary on Descriptional Complexity, $f(n) = 2^{\Theta(n)}$ (essentially; the lower bound is only ...
user avatar
3 votes

having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$

How does one prove that two regular expressions represent the same language? One approach is using axiomatizations of the equational theory of regular expressions. The equational theory of regular ...
user avatar
3 votes
Accepted

Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$

What you are looking for, the solution to part (b) is the last step of the State Elimination Method that converts a DFA/NFA/$\epsilon$-NFA into regular expression. Here is a short article that ...
user avatar
  • 33.1k
2 votes
Accepted

Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

Believe it or not the language $L$ is equivalent to: $L' = 1(0 \cup 1)^*1$ which is regular Proof: Given $x \in L'$, then $x=1^1w1^1$ with $w \in (0 \cup 1)^*$, so $x \in L$ (just take $n=1$) Given $...
user avatar
  • 12.2k
2 votes

Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

Let $x=1^kw1^k\in L$ (with $n=k$). Then, define $w':=1^{k-1}w1^{k-1}$, and we will have $x=1w'1\in L$ (with $n=1$). Try to use this trick to "remove" the $n$ in the question. After "...
user avatar
  • 10.7k
2 votes

Read regular Expression from NFA

The RE is wrong. It also includes abcb which is not in the language of the automaton.
user avatar
2 votes
Accepted

Describe regular expression

It seems I didn't understand the question. There is no regular expression for this language because it is not regular. You can prove it using the pumping lemma.
user avatar
  • 7,154
2 votes

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

$[0-9]*$ includes all finite strings of the digits including the empty string $\epsilon$ (Some books denote the empty string by $\lambda$). An integer, by definition, has at least one digit. Hence, $[...
user avatar
2 votes

Are this languages can be represented by regular expressions?

For question 1: try to come up with a proof that the language is not regular. Hint: Let your language be $L$ and suppose towards a contradiction that it is regular. Use the closure properties of ...
user avatar
  • 22.7k
2 votes

What is the regular expression for the language, {w | w does not contain the substring 11}

$0^*$ will generate any number of repetitions of $0$, and will also generate the empty string $\epsilon$. So, the problem with your expression is that $11$ is also accepted, since we can write it as $$...
user avatar
  • 10.7k
2 votes

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.
user avatar
2 votes

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 ...
user avatar
2 votes
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 ...
user avatar
  • 966
2 votes

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 ...
user avatar
  • 966
2 votes

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 ...
user avatar
2 votes

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

Hint: words in $\{ww\mid w\in\{a,b\}^*\}$ have even length.
user avatar
  • 7,154
2 votes
Accepted

Every non-regular language has a subset which is a regular language?

Your claim is true, so there is no counterexample. $\emptyset$ is a regular language and is a subset of every (non-regular) language.
user avatar
  • 22.7k

Only top scored, non community-wiki answers of a minimum length are eligible