# 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 𝑣}
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 ...
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 ...
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?
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, ...
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 ...
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 \}$, ...
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, ...
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 ...
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

The given alphabet is $$\Sigma = \left\{ a, b, c \right\}$$ I am looking for a nondeterministic finite-state machine which accepts the following words: $$L=\left\{w\in \Sigma^* \mid \exists x\in\Sigma:... 2 votes 3 answers 132 views ### Proving a language is not regular using the pumping lemma Let$$ L =\Big\{ \ ba^{2^k}b^{i_1}ab^{i_2}a\dots b^{i_k}a \ \Big|\ k\ge 1,\ i_j\ge1 \ ,\ 1\le j \le k\ \Big\}\ . $$Using the pumping lemma prove that L isn't regular. The answer given to this ... 2 votes 1 answer 72 views ### L_1 and L_2 are regular and we have a new language \text{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2\text{ s.t. }xu\in L_1\} prove that \operatorname{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2 \text{ such that xu\in L_1}\} is regular. So I was thinking proving this question by building an automata for ... 0 votes 1 answer 38 views ### Prove that L=\{a^n b^l : n \leq l\} is not regular by pumping lemma I'm currently trying to prove that L=\{a^n b^l : n \leq l\} is not regular by pumping lemma My proof: If we choose w such that w=a^P b^P, then since |xy| \leq p, y must be a^P, meaning it ... 0 votes 1 answer 46 views ### creating regular expressions from given language The first question is L_1 = \{w \in \{a,b,c\}^∗ \mid \text{w ends with ca}\} I started by creating a DFA for that for better understanding and then making a regular expression. and the regular ... 0 votes 0 answers 16 views ### Pumping lemma on a regular language with different variables I have this language L = \{a^i b^j c^k ∣ i,j,k \geq 0 \text{ and } i+j=k \} I dont know how to replace i,j,k  with the pumping length p, usually when I make a string s with the pumping length p I ... 0 votes 0 answers 24 views ### How can I prove that L´=\{uv|u,v\in\sum^*,vu\in L\} is regular if L is regular? [duplicate] For language L over alphabet \sum define language L´ as follows: L´=\{uv|u,v\in\sum^*,vu\in L\} Is then L´ also regular? I think that yes, because if we can take u and v as we want, we ... 1 vote 1 answer 21 views ### Is the language represented by the set of binomials following some rule regular? Consider a \Sigma = \{\binom{0}{0},\binom{1}{0},\binom{1}{1},\binom{0}{1}\} and a language L over \Sigma such that strings in the language have the "bottom row" of the string as the ... 1 vote 1 answer 36 views ### Solution verification: Proving that this language is irregular using the pumping lemma. Prove that the following language with \Sigma=\{a,b\}, is not regular using the pumping lemma: L=\{ba^{2^{k}}b^{i_1}ab^{i_2}...b^{i_k}a : k\ge 1, \forall j\space\space (1\le j \le k)\space\space ... 1 vote 2 answers 122 views ### Prove that the shift operation on regular languages preserves regularity I have the following question: I have seen the statement that for the Shift operation, defined as: Shift(L) = { yx | xy \in L} Where the following is mentioned: "For any regular language L... 1 vote 1 answer 18 views ### Solution Verification: Prove this using closure properties of regular languages. Prove that this language isn't regular using closure properties of regular languages: L=\{a^{j+1}b^kc^{j-k}:j,k,j-k\ge 0\} L is over \sum=\{a,b,c\}. My Solution: We define the homomorphism ... 0 votes 0 answers 32 views ### Proof of Pumping Lemma: Why can we set the pumping constant to the number of states? I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA. As such: The language ... 1 vote 1 answer 32 views ### Solution Verification: Regular expression that starts with a and doesn't contain aba pattern. Write a regular expression that starts with a and doesn't contain aba pattern. My Solution: If my expression doesn't contain aba, then it must not have a b alone in the middle of it before ... 0 votes 1 answer 47 views ### proof that L is regular Given that A is a regular language and B a regular or non-regular language, prove that L is regular:$$L = \{w | wx \in \text{A such that }x \in B\}$$We can say that L is a subset of A. Regular ... 1 vote 2 answers 36 views ### Constructing grammar for a^ib^j / i\neq j I want to construct a grammar for the following regular expression: a^ib^j / i \neq j. I did it the following way: S_1 \rightarrow aaSb | aaAb A \rightarrow aA | \epsilon S_2 \rightarrow aSbb | ... 2 votes 0 answers 24 views ### constructing grammar for 1*0*1(1+0)* I want to construct a grammar for the following regular expression: 1^*0^*1(1+0)^*. I did it the following way: S \rightarrow AB1C A \rightarrow 1A | \epsilon B \rightarrow 0B | \epsilon C \... 1 vote 1 answer 114 views ### a^m b^n c^n prove it's not regular/pumping lemma How to prove that L = \{a^mb^nc^n \mid n, m \geq 0\} is not regular by the pumping lemma My attempt: Let's suppose L is regular. There exists a pumping constant p, and we choose w = a^pb^pc^p ... 3 votes 1 answer 40 views ### FSM and regular language Here is a finite state machine which can be recognised with a regular language. The regular expression which I've got for this FSM is: (10(0+(10))*11+11+00*10(0+(10))*11+00*11)(0+1)* Is this correct? ... 0 votes 3 answers 95 views ### a^nb^n language vs a^nb^m I always read that \{a^nb^n \mid n>0\} is not a regular language because automata doesn't have memory, while \{a^nb^m \mid n, m>0\} is regular because we don't have to remember anything ... 1 vote 1 answer 29 views ### DFA conversion through state elimination and arden's method I have tried to convert the following DFA to regular expressions through two different methods: Arden's method, and state elimination one. I have arrived to two different regular expressions: Arden's ... 1 vote 1 answer 39 views ### Induction on automaton [closed] Let an automaton defined by the following transition table: 0 1 \rightarrowA A B \leftarrowB B A I have this finite automaton, and it recognizes the languages with only an odd number of 1s ... 0 votes 1 answer 37 views ### intersection of two regular expressions [closed] If we have two regular expressions L_1 = aba^*b^*c^* and L_2 = a^*b^*c^*ab, how do we get L_1 \cap L_2 get? I found the answer to be L_1 \cap L_2 = ab + abab But I don't know how it was ... 0 votes 1 answer 23 views ### Solution Verification: Prove or Disprove: If L is an irregular language and F is finite language, then F\cap L^+ is regular. Prove or Disprove: If L is an irregular language and F is finite language, then F\cap L^+ is regular. Note: L^+=\bigcup_{i=1}^{\infty}L^i. I will be attempting to prove this statement. ... 1 vote 1 answer 39 views ### Regular expression rules for union and concatenation with \epsilon and \emptyset I have four rules here that are true and I wanted to make sure I have a general intuition as of why. These aren't meant to be rigorous proofs, but rather simple explanations. Suppose R is a regular ... 3 votes 2 answers 69 views ### Solution Verification: There exists an infinite set of different irregular languages such that their union is a regular language. Prove or disprove: There exists an infinite set of different irregular languages such that their union is a regular language. My intuition led me to try to disprove, since if I had a set that is ... 0 votes 1 answer 50 views ### Understanding languages for Finite State Automata Hi I'm learning about finite state automata. I understand what a language is but I don't understand what this syntax is telling me about it. L = {\{a,b\}}^{*}{\{aa,bb\}}{\{a,b\}}^{*}  Could you help ... 0 votes 3 answers 53 views ### How can the following language be regular? Lets assume the language L=\{a^n b^m\} When we try proofing L is regular using the Pumping lemma and say w=xyz and thus for every w=xy^iz  , w has to be  \in L . now if we say y only ... 0 votes 0 answers 31 views ### How are all words over S in the language in this question? Let S = \{a, b\} and let X= \{w \mid \text{w is a word over the alphabet S}\}. For each language given below, list (if you can) two words which are in the language, and two words which are not ... 0 votes 1 answer 51 views ### computation by commuting I have some doubts about your paper Computing by commuting (abstract is copied below): What do these sentences say (my REMARKS on what I do not follow are numbered by 1,2): " the choice of a word ... 2 votes 2 answers 113 views ### Regularity of a language checker I have to check if this language is regular or not:$$L = \{w(bb)^nw^R:w\in\{a,b\}^* \land n \in \mathbb{N}\}$$My thoughts are if this language is regular so the RE for this is: (bb)^* where w and ... 0 votes 0 answers 60 views ### is {w in {0,1}* | #0(w) = #1(w)} a regular language? is L = {w in {0,1}* | #0(w) = #1(w)} a regular language? I've managed to prove it is context free, but this doesn't really help. I've also saw a hint (here - prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} ... 1 vote 1 answer 109 views ### Regular expression for a language string I'm trying to build a regular expression for this language:$$L=\{w\in\{0,1\}^*: \text{at least two} \ 0's \ \text{and at most two} \ 1's\}$$So, it's mean that this language has |w|_0 \geq2 and |w|... 0 votes 0 answers 48 views ### Proving a language is regular or not? I'm trying to understand how to prove a language is regular or not regular, for example this language:$$L=\{a^nb^m:n,m\in\mathbb{N}\land n+m=5 \} Is this language regular or not? My solution Using ... 1 vote