# Questions tagged [regular-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

1,030 questions
Filter by
Sorted by
Tagged with
11 views

### Determine if complement of non-regular language is context-free

I'm trying to understand if the complement of non-regular language is context-free. for example: $L=\{ 0^n 1^n │ n\ge0 \}$, I need to prove that the complement of $L$ is regular so $L'$ is context-...
39 views

### What does w ∈ a, b* mean?

What does $w ∈ a, b^*$ mean? The context is the language of an automation, which is $L=\{w∈ a, b^*|:|w|$ is even and the central symbols of $w$ are $aa\}$ I really don't understand what $w ∈ a, b^*$ ...
69 views

28 views

### Regular expression without subword 000 [duplicate]

what is the regular expression for the language above {0,1} that does not contain the subword 000? Thank you for your help!!
38 views

### Prove language of $0^n1^m$ is irregular for coprime $n,m$. [duplicate]

I need to prove that the language of $0^n1^m$ is irregular if $n$ and $m$ are coprime. (Or to disprove that) My attempt at this was to use the pumping lemma, and I've gotten $0^{n+(k-1)i}1^m$ after ...
83 views

### pumping lemma - union of regular languages

In the question, we have regular languages L1, L2 with the constant of the pumping lemma - n1,n2. Also, we have the language L = L1 + L2 with the constant n of the pumping lemma. I need to prove that ...
39 views

### union of regular language and non regular language

I have the languages $L_1 = 00^*\{1^n0^n \mid n \geqslant 0\}$ and $L_2 = 0^*1^*$. I know that $L_1$ is not regular and $L_2$ is. But is $L = L_1 + L_2$ is not regular? An extended explanation will ...
29 views

### How do these languages intersect the way they do?

So I have these languages: $$\begin{split} A_1 &= \{w1^{|w|}|w \in \{0,1\}^*\} \\ A_2 &= \{ww|w\in\{0,1\}^*\} \\ A_3 &= A_1 \cap A_2 \end{split}$$ $A_1$ and $A_2$ are irregular but it ...
18 views

### Prove that a class of regular languages is closed under an operation

We define an operation addone on any string in $\Sigma^*$ that adds a $1$ after the leftmost bit if such a bit exists. For example, $\operatorname{addone}(010)$ is $0110$, $\operatorname{addone}(00)$ ...
30 views

### Why is the minimal pumping length for $(01)^*$ equal to 1?

I see why the minimum pumping length is at most 2 (since 01 can be pumped). But why is this counterexample not valid? Let $A=(01)^*$ and assume it has pumping lenght $p=1$. Then lets consider the ...
37 views

### Complexity of determining the Hamming distance from a given word to a given regular language

Suppose $L \subset A^*$ is a given regular language (defined by the corresponding DFA). What is the best possible computational complexity of an algorithm, that for a given word $w \in A^*$ returns ...
62 views

### Prove that if L is decidable then half(L) is decidable too

Let L be decidable language, and let half(L) be: half(L)={u∣uv∈L s.t.|u|=|v|}. Prove that if L is decidable then half(L) is decidable too. I tried to build a Turing Machine to decide half(L) but none ...
20 views

### Using induction to show that the languages $\mathcal L(A)$ and $\mathcal L(G(A))$ are the same

Let $\newcommand{\perm}{\left\langle #1 \right\rangle}A = \perm{ Q, \Sigma, \delta, q_0, F }$ be a finite, nondeterministic automaton and $G(A) = \perm{ \Sigma, V, P, S }$ the grammar generated by ...
29 views

### How to prove that a language is not regular without the use of the Pumping Lemma?

I have an exercise to prove. Prove that $\{a ^ i b ^ j c ^ k \mid i, j, k \geqslant 0, \text{if$i = 1$then$j = k$}\}$ is not a regular language but that respects the conditions of the Pumping ...
27 views

26 views

### What does the “\” mean in this statement about regular languages?

I have having difficulty finding the meaning of the backslash in the statement. I don't know if it could be a division, an OR operator or something else. If someone could provide information about it, ...