# Questions tagged [regular-languages]

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

1,099 questions
17 views

### Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
46 views

51 views

### Closure of context-free languages under regular quotient [duplicate]

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?
535 views

### Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
41 views

### Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪ (rs)*. I think this is not true. And I believe this would always be true : (r ∪ s)* = r* ∪ s* I wanted to clarify this ...
83 views

### The equational theory of regular languages has no finite set of axioms for general alphabets

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms. Why does this imply that it has no finite set of ...
20 views

### Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
42 views

### If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?

I am confused interpreting the statement of this question: "If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?" Should the symbol "|" (such as) be understood as ...
18 views

### Prove that every infinite regular language has an undecidable infinite subset [duplicate]

I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due ...
17 views

### Trouble coming up with an expression to describe a DFA [duplicate]

This is a DFA that describes a language over {a,b} that only accepts a string if the number of a's in the string is not divisible by 3. I'm having difficulty coming up with an expression for it, I'm ...
92 views

65 views

### Proving that a Language is non-Regular

Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular. I was wondering if my intuition holds for proving this language as not regular: Let $q = \max(i, j) - \min(i, j)$. ...
78 views

### Show that C(n) = {a^k | k is a multiple of n} is a regular language

I came across this question in an exam book and was unable to find a solution: Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1. I wasn't able to ...
31 views

### Proving that language is regular or not [duplicate]

How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not: $\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$ I started with the ...
56 views

### Prove or disprove whether L is regular by definiton [duplicate]

Assume L is regular language, define 𝐿1 = {𝑣𝑤: 𝑣 ∈ 𝐿,𝑤 ∉ 𝐿}, prove or dispute L1 regular or not ?