# 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,178 questions
Filter by
Sorted by
Tagged with
11 views

### If $\mathcal{L}$ is regular, then prove that $\mathcal{L/3} = \{w ∈ Σ^∗|∃ x, y ∈ Σ^∗, wxy ∈ \mathcal{L}, |w| = |x| = |y|\}$ is also regular.

If $\mathcal{L}$ is regular, then prove that following language $$\mathcal{L/3} = \{w ∈ Σ^∗|∃ x, y ∈ Σ^∗, wxy ∈ \mathcal{L}, |w| = |x| = |y|\}$$ is also regular. $\mathcal{L/3}$ is the front $1/3$ ...
15 views

### Difficulty understanding a 1-tape TM program which solves and includes time analysis of the program

I need to sketch a 1-tape TM program which solves and also includes a time analysis of the program, e.g. 𝑂(𝑛), 𝑂(𝑛𝑙og 𝑛), 𝑂(𝑛3), etc.; 𝐿 = {𝑢#𝑣: 𝑢, 𝑣 ∈ {0,1}∗ and 𝑢 is a substring of 𝑣}
• 1
11 views

### Probability Expression With Nested Given That Operators

Does the expression $\Pr((X\ |\ A)\ |\ B)$ make any sense? I want to say that $\Pr(X\ |\ (A \cap B))$ is equivalent to $\Pr((X\ |\ A)\ |\ B)$, and thus also to $\Pr((X\ |\ B)\ |\ A)$, but I'm not sure ...
• 1,654
15 views

### I have to make a regular expression where : The language, over the lower case English alphabet, of words with at least 2 vowels

this is the expression that I made is this correct?? .(x)^+.(x)^+ + .(xx)^+. + (xx)^+.* + .(xx)^+ + .(x)^+.(x^+).
22 views

### Automata Regular Expression that remembers n iterations

Given is $L = \{\sigma_1 ~u~\sigma_2~v~\sigma_3 ~|~ \sigma_{1,2,3} \in \Sigma,~~ u,v\in \Sigma^*,~ |u|=|v|,~ \sigma_2=\sigma_3 ~or~ \sigma_2=\sigma_3 ~~\mathbb{but ~~ not ~~ both} \}$ I do not ...
• 654
54 views

### Prove $L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$ is a regular language where $L$ is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma$. Prove that the language $$L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$$ is regular.
38 views

### Finite state Kleene star machine

I want to represent finite-state machine but I have problems with opening brackets $(a^*dc^* + acd^*)^*$. Should it be $a^*d^*c^* + a^*c^*d^*$? Should I use the first or second image option?
• 1
65 views

### On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite ...
1 vote
44 views

### Proving that these two regular languages are equal

Consider the regular expressions $r_1 = (1+01)^* (0 + \epsilon)$ and $r_2 = (1^* 011^*)^*(0+\epsilon) + 1^* (0+\epsilon)$. I want to show that these the regular expressions generate the same language, ...
• 503
1 vote
31 views

### Prove language irregularity using Nerode theorem

Let $L=\{b^ma^n|m \space and \space n \space are \space coprime \}$ using Nerode theorem prove that $L$ is irregular. From Nerode theorem I know that $L$ is regular if and only if the number of ...
• 373
20 views

### Prerequisite on $L$ so $L^*$ is finite

I need to find a sufficient prerequisite on formal language $L$ over alphabet $\Sigma$ so that $L^*$ is a finite language. I say that language $L^*$ is finite if and only if $L = \{ \varepsilon \}$, ...
• 373
18 views

### Finding an infinite language with finite equivalence classes

Let $\Sigma$ be an alphabet and let $L$ be a language on $\Sigma$. If it is known that all the equivalence classes of $R_L$ are finite, is $L$ regular? If definitely yes, prove. If definitely no, ...
• 373
1 vote
29 views

### Finding equivalence class for $R_L$ of a regular language

Let $\Sigma = \{ a, b, c\}$, $$L = \{w\in\Sigma^*\mid w \text{ starts with ab and ends with ab}\},$$ i.e. $L = ab(\varepsilon + (a+b)^*ab)=ab+ab(a+b)^*ab$. I need to find a regular expression ...
• 373
23 views

### Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma

How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma? I know how to prove ...
1 vote
29 views

### Find NFA for the language $L_1$ of all # that can be replaced by string of size 3 that would be in language $L$

Let $L$ be a regular language, and let $$L_1 = \{u_1\#u_2\# \dotsm \#u_n \mid ∃v_1,v_2,…,v_{n-1} \in \Sigma^3 \text{ such that } u_1v_1u_2 \dotsm v_{n-1}u_n \in L \}$$ where $\# \notin \Sigma$. For ...
26 views

1 vote