# Questions tagged [regular-languages]

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

1,561 questions
Filter by
Sorted by
Tagged with
568 views

### Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an ...
2k views

### Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \}$ Are regular / context free languages closed under this operation ? For regular languages I ...
501 views

### How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
71 views

### Complement of non-deterministic finite automation [duplicate]

Given an NFA, is there a way to “take its complement” and obtain an NFA that recognizes the complement language?
127 views

### The language of all borderless words

Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please? A word ...
511 views

2k views

### Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
288 views

359 views

998 views

### Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
2k views

278 views

### Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$. ...
131 views

### For regular languages A and B, determine whether B might match early in (A B)

I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
3k views

### Star free language vs. regular language

I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example? (from wikipdia) Lawson defines star-free ...
408 views

### Why is the subset of palindromes of a regular language context-free?

Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language? Trying to understand the approach to determining whether a regular language is context-free.
373 views

### Pumping Lemma for regular languages proof doubt - Sipser Book

I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there. In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ ...
156 views

### Deciding whether a given language is regular [duplicate]

I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes: Decide if the following language is regular ...
3k views

### Show that the Kleene star of any unary language is regular [duplicate]

An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \{ 1 \}$ Here's my reasoning : $L$ is regular $\implies$ $L^*$ is regular (closure ...
2k views

### Can we say anything about the complement of a regular language?

Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the ...
69 views

15k views

### Are the non-regular languages closed under reverse, union, concatenation, etc?

My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)
4k views

5k views

### DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

How do we find all equivalence classes of $\mathsf{R_L}$ for a language? Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$. Here's an ...
### How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?
I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma: $L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$ Does this indicate that $S = 2$, so we ...
### If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?
Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also ...