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
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) $\...