# Questions tagged [regular-expressions]

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

573 questions
Filter by
Sorted by
Tagged with
131 views

### Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.) Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language? This question ...
22 views

### Pseudo-random regex-searchable function

Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties: $f$ is efficiently ...
48 views

### Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪ (rs)*. I think this is not true. And I believe this would always be true : (r ∪ s)* = r* ∪ s* I wanted to clarify this ...
79 views

### Validating attempt on NFA to Regular Expression

So i tried turning the following NFA into a GNFA (first attempt). Please don't ask why i chose to do such a complex NFA on my first try, i just like the challenge i guess? ab is the concatenation of ...
179 views

57 views

### Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
415 views

### Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite? [duplicate]

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma? Additionally,is there an ...
53 views

### Can three regular languages be concatenated?

I can't seem to find anything about this and I wonder if I'm asking a silly question. If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated? If yes, would ...
28 views

### DFAs that must reach a certain state at least once

I was given this question: Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0. Define the language A⊆Σ* to ...
104 views

### Counter-example to regular expression statement

Show a counter-example to disprove the following statement: If $R1$ and $R2$ are two regular expressions, then $L((R1 \cup R2)^*) = L(R1^* \cup R2^*)$.
49 views

### Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
156 views

### Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
549 views

### Unambiguous grammar for regular expressions

How to define a non ambiguous grammar for regular expressions on the $\Sigma = \{a,b\}$ alphabet? Given that: If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols A regular expression ...
275 views

### Generating finite automata from regular expression [duplicate]

Right now I am trying to learn how to work with automata and regular grammar, and I encountered the following exercise: $(1^*01)11$ I found the following solution, but I am not really sure if it's ...
1k views

### How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form: To a regular expression equivalent. What I have tried was using arden's rule. However I ...
237 views

### Difference between NFA and NBA

NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages). I think the example ...
2k views

### Regular expression for the language containing neither aa nor bb

I want to create a regular expression for the language $L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$. I've tried various things, but I can't seem to get the correct regular ...
342 views

### Whether equivalence of different types of automata is of P-type?

I came across following problem: Which of the following problems is/are P-problems? (I) Equivalence of DFA's (II) Equivalence of NFA (III) Equivalence of regular expressions Now I know I ...
36 views

### How do you get a regex from this DFA? [duplicate]

I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA: And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove ...
123 views

### Prove this language is non-regular [duplicate]

I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated. Prove using the Pumping Lemma that the following language is not ...
46 views

65 views

### How to find a regular expression

I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules? For example, for the language $L \subset \{ a,b\}^*$ which ...
265 views

### How to build a parser for syntactic analysis of regular expressions?

Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages? My guess ...
63 views

### Do we need regular expression first or finite state automata in lexical anlysing? [closed]

I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, ...
530 views

### Is the difference between two regular expressions a new regular expression?

Let say the following: Given Ax and Bx two literals which represent POSIX regular ...
421 views

### Why are regular expression quantifiers greedy by default?

I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. ...
598 views

63 views

### Recurrence relation for a star and a dot wildchar pattern

. Matches any single character, * Matches any sequence of characters (including the empty sequence). dict = ["cat", "cats", "...