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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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$ ...
user avatar
0 votes
0 answers
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 𝑣}
user avatar
  • 1
-1 votes
0 answers
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 ...
user avatar
  • 1,654
-2 votes
0 answers
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^+).
user avatar
-1 votes
0 answers
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 ...
user avatar
  • 654
0 votes
0 answers
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.
user avatar
-1 votes
0 answers
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?
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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, ...
user avatar
  • 503
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 \}$, ...
user avatar
0 votes
0 answers
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, ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
26 views

Creation of nondeterministic finite-state machine for a word which doesn't contain a certain symbol

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:...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 55
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 ...
user avatar
  • 111
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 ...
user avatar
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 ...
user avatar
  • 43
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 ...
user avatar
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 ...
user avatar
  • 1,713
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 ...
user avatar
  • 2,029
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$...
user avatar
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 $...
user avatar
  • 2,029
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 ...
user avatar
  • 1
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 ...
user avatar
  • 2,029
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 ...
user avatar
  • 1
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 | ...
user avatar
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 \...
user avatar
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$ ...
user avatar
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? ...
user avatar
  • 33
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 ...
user avatar
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 ...
user avatar
1 vote
1 answer
39 views

Induction on automaton [closed]

Let an automaton defined by the following transition table: 0 1 $\rightarrow$A A B $\leftarrow$B B A I have this finite automaton, and it recognizes the languages with only an odd number of $1s$ ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 2,029
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 ...
user avatar
  • 37
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 ...
user avatar
  • 2,029
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 21
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 ...
user avatar
  • 3,578
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 ...
user avatar
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)} ...
user avatar
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|...
user avatar
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 ...
user avatar
1 vote
1 answer
25 views

Using complement to create a DFA with a specific condition

In my understanding, the complement of an automaton is when the final states become non-final and the non-final states become final. I tried to apply this method to create an automaton that never ...
user avatar
0 votes
1 answer
42 views

What are general tips for generating grammars for context free languages?

Perhaps, this does not have a "correct" answer, but what are general tips for creating context free grammars for context free languages? I know there is usually no step by step solution to ...
user avatar

1
2 3 4 5
24