Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-expressions]

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

0
votes
0answers
13 views

Extended regular expression and intersection of languages of DFAs

I'm new with extended regular expression and I want to know if there are connections with the intersection non-emptiness problem of languages of DFAs. I would like to see some research articles on ...
0
votes
1answer
45 views

In RegExr, why is regex OR in JavaScript sometimes not commutative?

On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same. The first one matches only $a$'s and the second one $b$'s. Is ...
1
vote
3answers
51 views

Regex for bit strings with at least two zeros but no consecutive zeros

This is what I have: $$(1^*011^*011^*)^*\,.$$ But I don't think this is accounting for an odd number of zeros, like "$10101010101111$". I think I have the right expression that satisfies no 2 ...
2
votes
1answer
33 views

Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

For regular languages $A,B\subseteq\{0,1\}^*$, is $$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$ regular, where $|x|_1$ means the number of appearances of 1 in the word $x$? i need to ...
0
votes
1answer
72 views

Is this concatenation of two FA done right?

$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$ Details: Consider ...
2
votes
2answers
277 views

Language of all strings that has exactly 1 triple b

I am new to automata and learning to make regular expression for languages. But I have been stuck on this one. Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
0
votes
0answers
24 views

Context-free grammar for the language $L_a=\{w:w \neq uu, u\in L((a + b)^*)\}$ [duplicate]

To my understanding, $(a + b)^*$ is a regular expression equivalent to the language $\{a, b\}^*$. Thus, $L_a=\{w: w \neq uu, u\in L(\{a, b\}^*)\}$. I'm trying to simplify the language even further so ...
1
vote
1answer
19 views

Determining initial and final states from FA diagram

I am new to automata. And learning to find concatenation of two FAs. But this one has confused me I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
0
votes
1answer
46 views

regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

$r_1=\Lambda+(a+b)^*b$ $r_2=(b+aa^*b)^*$ $r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$ For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
0
votes
1answer
28 views

Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

I need help understanding the language L above. These are my understanding: - w = uu is a concatenation of ...
0
votes
0answers
13 views

Regex engine: A polynomial algorithm for backreferences?

During my search for a way to integrate efficiently backreferences (using backtracking) into a text-directed regex engine, I found a paper entitled Extending finite automata to efficiently match Perl-...
1
vote
0answers
25 views

Extending Thompson's NFA algorithm with backreferences

I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
1answer
29 views

Finding a correct regex for the strings with at least two $0s$

I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $0$'s over the alphabet $\Sigma = \{0,1\}$." I made this: $(0+1)^*0(0+1)^*0(0+...
1
vote
1answer
24 views

In which environment we use NFA(Non Deterministic Finite Automata)?

We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
2
votes
1answer
55 views

Why does the concatenation operation imply the empty string?

I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular ...
0
votes
0answers
14 views

Example of a language with linear NFA, but exponential DFA [duplicate]

So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
10
votes
3answers
2k views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem There is no easy way to get a permutation with a regex. Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters. Regex: Regular ...
1
vote
0answers
30 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
1
vote
1answer
34 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
1answer
29 views

$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1

$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^R = w, |w| = n \}$ Informally x is palindrome of length n where $\Sigma = \{0,1\}$ I'm having a hard time understanding this ...
1
vote
2answers
52 views

Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it. This is language $L$ which is introduced with grammar: $$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$ ...
1
vote
1answer
35 views

Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$

Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$. Give a regular expression that denotes $L_1$, and justify its correctness Attempt Believe this ...
0
votes
0answers
19 views

Regular expression for a set of strings (of 1's and 0's) whose number of 0's is divisible by five?

I thought this might be a solution, but it seems fishy (and inefficient): (1*01*01*01*01*01*)*.
-1
votes
1answer
14 views

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
1
vote
0answers
58 views

What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
1
vote
2answers
45 views

Regular expression for words where the same symbol can repeat at most two times consecutively?

Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol? For example, I can't have ${baaab}$ nor ...
0
votes
2answers
39 views

Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
0
votes
1answer
33 views

Can this DFA be converted to a regular expression? [duplicate]

I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
0
votes
2answers
55 views

Does the distributive property apply to regular expressions?

Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does $$ (q_1a+q_2b)c=q_1ac+q_2bc $$ hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$? Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ ...
3
votes
2answers
51 views

DFA that accepts any integer $n$ such that $n \bmod 7 =1$

It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA. Is there smart way to do it without a machine which has memory ...
1
vote
1answer
53 views

Find the number of strings in the language $(∅∅^∗ + ∅)$

Consider the language $L = \emptyset\emptyset^∗ + \emptyset$. How many words does $L$ contain? Zero or one? Note: $\emptyset^∗ =\{\epsilon\}$.
1
vote
1answer
37 views

How do I convert the following GNFA to regular expression?

Here is a GNFA I made from an NFA. I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
2
votes
0answers
62 views

Which transducer models replacement in regex?

I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with ...
0
votes
0answers
17 views

Derivatives of Extended Regular Expressions

I'm trying to formulate the derivatives of a few extended regular expressions: $[c_1, c_2, . . . , c_n]$ -- a range of characters $r^{n..}$ -- r repeated n or more times (where n ≥ 0) $r^{n..m}$ -...
0
votes
2answers
32 views

How to deal with character set in regular expression?

In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
1
vote
1answer
43 views

Regex for at least three 1's and at most four 0's

The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's. I've come up with a method that enumerate every possible number of 0's: $$111^{+}+0111^{+}+1^{+}...
2
votes
1answer
44 views

How to Apply Elementary Axioms from Kleene Star to an Inequality

Axioms For * \begin{align} 1 + aa^* &\leq a^* \\ 1 + a^*a &\leq a^* \\ b + ax &\leq x \to a^*b \leq x \\ b + xa &\leq x \to ba^* \leq x \\ \end{align} Elementary Results \begin{...
1
vote
1answer
68 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
0
votes
1answer
42 views

Different iterations of regular expressions

A four-part question dealing with formal languages and regular expressions: How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string? How ...
0
votes
1answer
73 views

Trying to simplify a particular regular expression

The question is as follows $$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$ But I am unable to solve this regex expression. My answer is as follows: \begin{alignat*}{2} (a^* + (ba)^* )^...
0
votes
2answers
67 views

Does there exists a finite automata for the given language?

The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as: $L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
2
votes
1answer
42 views

Proving formula for derivative of Kleene star

Prove that for any symbol $a$ and regular expression $r$ it is true that: $$\partial a(r^* ) = \partial .a(r)(r^* )$$ My attempt: Induction on regular expression $r$ Base cases: 1) $\...
0
votes
0answers
30 views

regular language for NFA [duplicate]

I'm trying to find the w-regular language of this NBA. In 'Principle of Model Checking' - Book there's an algorithm for this problem: 1. Take the NBA as NFA and create the regular language to get from ...
0
votes
0answers
50 views

Regular expressions - Do i need the $*$ inside $()^*$-brackets?

Do i need the $*$ after the first $B$ in this regular expression $(B^* + C)^*$ ? Do i need the $+$ after the first $B$ in this $\omega$-regular expression $(B^+ + C)^\omega$ Stated differently: Is $(...
3
votes
1answer
31 views

Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this? I've tried the pumping lemma but I don't think it applies here. I've also tried ...
1
vote
1answer
45 views

Proving equivalency of regular expressions

x,y are regular expressions, prove this: (xy+x)$^*$x = x(yx+x)$^*$* (* in this expression is kleene star) I am looking for a method that is applicable to prove such questions. I know that proof ...
4
votes
1answer
67 views

Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression? The way I solved this problem is to first convert the NFA ...
2
votes
1answer
67 views

Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?

Consider the following set constructed with a regular Kleene-star operation: $$ \{10^n \mid n\geq1\}^* $$ Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but ...
2
votes
1answer
31 views

Regular expression for capturing a “C-style” string

I have started to learn automata theory and languages. I am new to regular expressions. As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
2
votes
2answers
218 views

Is DFA and Regular Expression equivalent?

The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that? If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...