# Questions tagged [regular-languages]

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

1,663 questions
Filter by
Sorted by
Tagged with
9k views

### Why is the complement of a language that is not regular also not regular?

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
205 views

### How many languages are described by a regular expression?

How many languages can a Regular Expression describe is it only one or infinite? I have tried to google it but i haven't found any answer? I know that a Regular Expression describes a Regular Language?...
76 views

### If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular?

If $L$ is some language and $\{ww^R \mid w \in L\}$ is a regular language then does $L$ have to be a regular language?
3k views

### Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
1 vote
46 views

### What is the connection between finite automata and logic (sequential calculus)?

Languages recognized by finite automata are exactly those definable by sentences of the sequential calculus, and also exactly those definable by rational expressions (also called regular expressions) ...
395 views

### Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1 vote
48 views

66 views