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 ...
