# Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

1,128 questions
58 views

### Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it. This is language $L$ which is introduced with grammar: $$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$ ...
17 views

### Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
69 views

### What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
44 views

### Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
60 views

### Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?
86 views

### Prove regular languages are closed under $f(n) = 2^n$ and $f(n) = n^2$

Suppose $R$ is a regular language, let $f(R) = \{ w |$ $\exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $f(R)$ is regular for $f(n) = 2^n$ and for $f(n) = n^2$. I've ...
89 views

### The reverse DFA is not working as expected

Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it: And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
71 views

58 views

### How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
41 views

### Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
38 views

### Can this DFA be converted to a regular expression? [duplicate]

I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
21 views

2k views

106 views

360 views

### Is DFA and Regular Expression equivalent?

The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that? If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...