Questions tagged [regular-expressions]

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

849 questions
Filter by
Sorted by
Tagged with
36 views

Using SMT solvers to parse regular academic expressions

I am interested in solving the problem of building a binary tree based on a regular expression containing letters of the Latin alphabet, parentheses, alternative, iteration and option (question mark). ...
13 views

Let A be the language of strings such that every character in an even position is a 0 [duplicate]

Let A be the language of strings such that every character in an even position is a 0. Give a regular expression for A.
40 views

FSA for 'closure' of a language; how to represent?

Is my interpretation of this correct? I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA. In order to do so, would I draw a new edge from the ...
• 87
1 vote
47 views

Quickly converting a regex into a minimized DFA

Is there some sort of algorithmic way to quickly convert a regex into a minimized DFA? I am able to somehow "guess" the DFA by playing around with the regex (as shown in the image, where the ...
116 views

Why $(a+b)^* = (a^*b)^* a^*$

I have seen on a book that for regular expressions it holds the equality $(a+b)^* = (a^*b)^* a^*$ but I am not seeing why. It is clear that the language generated by $(a+b)^*$ contains $(a^*b)^* a^*$, ...
1 vote
83 views

How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows: Based on this definition, how can I formally prove that any regular ...
• 113
27 views

Formal regular expression equivalent for this programming regex

Consider these Regexes written in Julia (they should be equivalent in Python): ...
• 195
23 views

Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
• 61
72 views

• 57
43 views

How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the Question here it is said that $|xy^2z|<2^{p+1}$ Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
• 57
596 views

What does empty string ε actually mean?

I came across this weird expression while learning about regular expressions. $R^+ \cup \varepsilon = R^*$ why does doing union with an empty string makes this regex go from 1 or more to 0 or more?
• 71
2k views

Converting Regex to DFA

People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach). Is there a simple/intuitive, yet ...
79 views

How to work thompson's construction algorithm?

Could someone explain to me, through an example, how the McNaughton–Yamada–Thompson algorithm works in a way that I can understand? Thank you in advance for your helpful response!
35 views

If a person accidentally deletes a few letters when they try to type "IDAHO" or "ILLIONOIS", then when is state name unclear or ambiguous?

The Short Version of my Question The following two regular expressions represent two sets of strings. REGEX EXAMPLES OF STRINGS OF TEXT THAT MATCH THE REGEX ...
42 views

Flex's NFA Determinization Algorithm

I am trying to understand how the algorithm used by Flex works. I refer to the determinization procedure producing the output DFA. The algorithm is publicly available and contained in Flex's source ...
• 543
85 views

Formally Verify if a Sequence of Regex-Based Modifications is Idempotent

I'm performing a sequence of text formatting using regex in Python. I'm curious to know if it's possible to formally verify whether a single (or a sequence of) regex modification(s) is idempotent, ...
• 113
36 views

How does a regular expression match .+x?

A quick test shows what I'm describing: > const text = 'foobarhelloworld' > const pattern = /.+or/ > text.match(pattern) //=> 'foobarhellowor' What is ...
• 2,265
1 vote
36 views

What is the minimum length word accepted by the product of these simple loop automata?

Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^*$ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
• 548
272 views

Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'

I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like: After a lot of ...
145 views

Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?

So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
49 views

Binary combinatorics with rank

I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values). Also, I want to rank and unrank these subset of values (in ...
• 25
62 views

Regular expression for binary string containing no instances of 01

In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
1 vote
113 views

How to simplify this regular expression?

How do i prove that the regular expression $$a^*(ba^*)^*$$ is the same as $$(a+b)^*$$. Is there a way to prove this using regular expression identities?
• 11
89 views

For each of the following languages, give a regular expression over {a, b}

$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
33 views

Prove the language $a^n b^m$ where $m$ is a multiple of $n$ is not regular

Consider the problem Show $L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$ is not regular. I attempted the following. Assume $L$ is regular. Then there is a natural number $p \geq 1$ such ...
• 195
1 vote
96 views

The language of chains with twice as many $a$s as $b$s is regular?

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem: Let $L$ be the language of all words that ...
• 195
214 views

• 115
14 views

What algrorithm computes a mutally exclusive partitioning from two regulair expressions?

The Question A regular expression, such as AL+[EYI]+, represents a set of strings. ...
1 vote