Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

Filter by
Sorted by
Tagged with
1 vote
1 answer
40 views

Regex where all strings containing an even number of 0's:

Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is $$(1^*+01^*0)^* $$ But it is also $$1^*(01^*01^*)^*$$ Can we prove that they ...
0 votes
0 answers
16 views

When converting a "empty string" regular expression to finite automata, are FA with 2 states vs 1 state equivalent?

Let's say we have a regular expression, R = $ε$. If we wanted to convert this to finite automata ( NFA or DFA ) which of the following would we use? Have 2 states: q0 ( start state ) and q1 ( accept ...
0 votes
0 answers
9 views

RE to NFA conversion JFLAP [closed]

Having this regular expression ((0 + 1)(11)* + 0)* I get this NFA according to me: I'm trying to compare it with the RE on JFlap and it says it's not equivalent ...
0 votes
1 answer
19 views

Regular Expression of {w : w contains an even number of 0s and exactly two 1s}

I know the answer if it was OR would be (1*01*01*)* U 0*10*10*, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can'...
0 votes
0 answers
10 views

Regular Expression of {w : w contains exactly two 0s and at least two 1s} [duplicate]

I have this 1^*011^*011^* and haven't been able to think of it differently. Can you please help me see how I can get this input 0011 and 1100 correct?
3 votes
0 answers
49 views

Reference request about equivalence of automata / regular expressions up-to a language

The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
1 vote
1 answer
32 views

Is it true that $R.L^* + L^* = R + L^*$?

I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further. I want to ...
  • 15
0 votes
1 answer
43 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
0 votes
0 answers
51 views

What is a regular expression that describes whether an integer w is a multiple of 6?

Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
0 votes
0 answers
33 views

How does the regular expression '^(a+)+$' lead to this specific NFA?

OWAPS has an article on ReDoS (archived). In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities. They provide this illustration of ...
1 vote
0 answers
45 views

What is the formal definition of a combinational logic?

Question Background A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35): The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
0 votes
1 answer
36 views

Convert regex for comma separated value to CFG grammar

I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
0 votes
1 answer
36 views

When converting DFA/NFA to regular expression, where the DFA/NFA accepted empty string, is it okay to not have empty string as kleene star?

Let's say that we have a DFA, where the initial state was also the accept state. Meaning the DFA accepts the "empty string". Now, let's say that we convert the DFA to regular expression $R$, ...
0 votes
1 answer
40 views

Does every regular expression describe only 1 language?

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it Also, $...
0 votes
1 answer
58 views

Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem: Since, we have 3 accepting states, we would find 3 ...
0 votes
0 answers
21 views

How to reduce this regular expression: a* + a*bb* + a*bb*cc* + a*cc*?

I know minimizing regular expressions is PSPACE-HARD but we can still use identities to minimize regular expression. I can tell the reduced version of this would be a* b* c* by looking at the NFA, my ...
0 votes
1 answer
26 views

How to make a recursive definition for a given predicate?

I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression: $r=\emptyset$ $r=\varepsilon$ $r=a:\...
0 votes
1 answer
49 views

Context Free Grammar Advantages

I am currently learning about context-free grammar, however, I am confused as to why context-free grammar is used over regular languages(Regular expression) and what makes CFG more powerful. Even ...
1 vote
1 answer
39 views

Check whether a regular expression is correct

I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct? ...
  • 150k
-5 votes
1 answer
75 views

regex for {w ϵ {a,b}*: |w| mod 3 =0}

I think this is what the regular expression would be. (aaa U aab U aba U abb U baa U bab U bba U bbb)*
  • 1
0 votes
1 answer
34 views

Regular grammar such that it rejects keywords

I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable. Def: A variable can be any combination of characters, ...
  • 1
4 votes
0 answers
69 views

Inverse operation to concatenation for regular languages

I'm currently in need of the inverse operation of the concatenation of 2 regular languages. Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
0 votes
2 answers
67 views

Language to regular expression to prove it is regular

I'm trying to find a regular expression to describe the following language: $\{a^n xa^n | n≥1,x ∈ Σ^* \}$ where $Σ$ = {a,b} So far I've come up with $aa^* (aUb)^* aa^*$ but I don't think that accounts ...
  • 103
2 votes
1 answer
35 views

How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?

How to prove that for any words $w_1, ..., w_n$ on alphabet $\{0,1\}$ the regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
0 votes
1 answer
45 views

Asked to write a regular expression for a language but I am confused about the teachers given solution. (all strings NOT ending in 01)

The problem reads as follows: Write a regular expression for the following language on {0, 1}: $\bullet$ all strings not ending in 01. The solution my teacher gave is (0+1)$^{*}$(00+10+11)+0+1+$\...
  • 1
0 votes
1 answer
70 views

Are all non-context-free language infinite?

Are all non-context-free language infinite?
  • 1
1 vote
1 answer
164 views

Regular Expression Equality

I am wondering about this small question, why aren't these regular expressions equal? $(a+b)^* a^*$ and $(a^* b)^* a^*$
1 vote
1 answer
48 views

Regular expressions cannot be used to express context free grammars. Is there a similar notation that can?

Regular expressions are a powerful practical tool for string processing. But there are simple examples of useful string processing tasks (like, say, removing brackets from an expression ...
0 votes
0 answers
23 views

Regular expression for strings that do not contain the substring $aa$ and contain an even number of $a$'s [duplicate]

I am trying to find the regular expression for the set of strings over the alphabet $\{a,b\}$ that: do not contain the substring $aa$ and contain an even number of $a$'s Such examples include: $...
0 votes
1 answer
92 views

How to convert the regular expression $\emptyset^*$ to an NFA?

The question is to convert the following regular expression to an NFA: $\emptyset^*$. I know that the symbol phi in Theory Of Computation means an empty set. But what does phi^* mean?
0 votes
1 answer
48 views

Regular Language to Regular Expression

Let's assume I have the following regular language: L = {1,0}*{010}{1,0}* I would like to convert this to regex for a program. Would the equivalent regular expression for this be: ((0+1)*(010)(0+1)*) ...
9 votes
4 answers
1k views

Non-regular language whose prefix language is regular but not the whole set of words

I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
0 votes
0 answers
56 views

proof that there exists a regular expression r for every NFA with only 2 states

Let L be a regular language. Then there exists a regular expression r such that L = L(r). Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me: Let ...
  • 89
0 votes
1 answer
106 views

Describing the Language of a DFA with 7 States

So in my attempt to convert the following DFA into a regular expression, I ended up with ((ba)*(ab(ab)*)*(aa(ba)*a)*)*. The exercise I'm following wants me to ...
1 vote
1 answer
46 views

Are both regular expressions correct for the given DFA with three states?

Are both regular expressions correct for the following automaton? $$(\lambda+ a a^*b(ab)^*)(\lambda + b(a+b)^*)\\ \ \\ (a a^*b)^*(\lambda + b(a+b)^*)$$ The first one is the solution provided by the ...
  • 89
0 votes
0 answers
28 views

Power of regex extensions [duplicate]

It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
0 votes
2 answers
1k views

Regex for string does not contain the substring "110"

Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)? Write a regular expression for the language L = {w | w does not contain 110} So, the answer I get is: $(...
  • 33
0 votes
1 answer
41 views

Confused by Sipser's proof of equivalence of R and NFAs

I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
  • 33
0 votes
1 answer
136 views

DFA and NFA with 2 Substrings

I am preparing for my CS exam and found this question in a collection of old exams: Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string. I thought, ...
0 votes
1 answer
68 views

regex find substring matches in text

I have written a regex engine and it can match whole strings to a pattern without a problem, i.e.: match(E, w) and it returns ...
  • 1
-2 votes
1 answer
51 views

Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
  • 239
4 votes
1 answer
103 views

Are the set of all Bitcoin addresses a context-sensitive language?

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
-1 votes
2 answers
1k views

Regular Expressions with at least 3 b's and at most 2 a's

I am not a Regular Experssion expert, but my request is simple: I need to match any string that has at least 3 characters of B and at most 2 characters of A so for example: ...
0 votes
1 answer
94 views

How would I design a State Diagram (FSM) for a AC unit?

Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question: The AC should only turn on if a person is detected in ...
3 votes
2 answers
1k views

Length of a regular expression

What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count? For ...
1 vote
2 answers
291 views

NFA to recognize the language ${ab}$

In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
  • 113
1 vote
1 answer
100 views

Prove that the language of regular expressions is not regular

I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of ...
1 vote
1 answer
574 views

Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?

I understand why L2 is not a regular language. We can use the pumping lemma to prove it In the case of L2: assume n = 1 and string = ab We assume that L2 is regular, so it has "pumping length&...
3 votes
4 answers
2k views

What exactly is pumping length in pumping lemma?

Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and ...
-2 votes
1 answer
55 views

How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method I end up with this: My ...

1
2 3 4 5
16