Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
0
votes
0answers
21 views
Finite State Automata for English regular main verbs
I would like to build an FSA to recognise english regular main verbs. E.g. walk, play, call, look, etc... with following morphological forms: (1) base form, (2) third person singular (-s), (3) present ...
0
votes
0answers
14 views
What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?
I would like to know some ...
-3
votes
2answers
28 views
DFA accept 00 as a substring
How can design this question if we have an equation like that
={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
0
votes
1answer
29 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
0
votes
0answers
23 views
How use generalized suffix tree to match prefix string?
I know that generalized suffix tree can match substring for a given pattern.
But I have need a data structure which is able to
match prefix of many strings.
match sub string of of many strings.
For ...
0
votes
2answers
25 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
0
votes
0answers
19 views
Formal Class of Languages Describable by .NET Regular Expressions
This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
1
vote
1answer
35 views
Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11
I got that I can get (1) followed by not (1) like this
$$ (0+2)^*1(0+2)^* $$
From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ...
3
votes
1answer
31 views
Regular expression for words containing single 1 and even number of 0s
What would be a regular expression for the language of words containing a single 1 and an even number of 0s?
0
votes
0answers
21 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
54 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
79 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
36 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
77 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
303 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” ...
-1
votes
0answers
26 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
26 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
47 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
31 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
26 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
39 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
26 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
56 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
16 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
34 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
37 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
31 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
53 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
39 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
15 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
59 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
51 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
57 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
58 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
55 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
48 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
65 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
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
48 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
45 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{...
3
votes
3answers
97 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
80 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
72 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
49 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) $\...
