Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
5
votes
1answer
179 views

Direct conversion from regular expression to MSO

A language $L \subseteq \Sigma^*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\{0, \dots, n-1\}, <, (P_a)_{a \in \...
-2
votes
1answer
482 views

What is the regular expression for strings containing at least one a and at least one b? [duplicate]

$L = \{w \in \{a, b, c\}^*\mid w\text{ contains at least one }a\text{ and at least one }b\}$. what's the proper regular expression for the following language?
0
votes
1answer
186 views

All finite languages can be decribed using a regular expression? [duplicate]

I have a question. All finite languages can be decribed using a regular expression?
2
votes
1answer
44 views

Generating all words of length $n$ avoiding $A^2$ and $B^3$

I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing? I ...
2
votes
1answer
322 views

Concatenation of two regular languages

In a question, it is given that L is a finite language over the unary alphabet and L+ is not regular. We know that L+ = LL* Since L is finite, it must be regular because all finite languages are ...
0
votes
0answers
25 views

NFA to RE question [duplicate]

Converting the following NFA to Regular Expression. Quick question: Do I have to add a new initial state as Q1 is accepting an incoming edge with 0+1 from itself? Method used: State elimination ...
1
vote
1answer
100 views

Regular expression that have the same number of 0 and 1

I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I cant figure out how to solve it. Could I get a hint on how to construct a regular expression ...
-1
votes
1answer
472 views

Regular expression of a language over {a,b} which does not contain substring bbb [duplicate]

I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
6
votes
1answer
96 views

Relative succinctness of NFAs and regular expressions

What is known about the succintness of NFAs, relative to regular expressions? In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the ...
0
votes
1answer
508 views

Regex for divisibility by 123 in binary strings

Is there a regex that checks for divisibility by 123 in binary strings? This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative ...
2
votes
1answer
79 views

Is there a way to find a simple regular expression for this language?

Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is ...
0
votes
1answer
62 views

Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product. $L_1^+ \bigotimes L_2^+$ ...
0
votes
0answers
247 views

Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
0
votes
2answers
599 views

Regular expression for string with substring 010 and ending with 01

How can one design a regular expression for given string in title ? Also how can we draw DFA of that regular expression? I've tried many expressions but couldn't succeed, please help.
1
vote
1answer
107 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
0
votes
1answer
636 views

Do all Regular Expressions describe Regular Languages?

I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent ...
4
votes
1answer
591 views

Cartesian product of regular expressions?

My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of <...
1
vote
1answer
404 views

Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression. On inspecting the given automata, I started deducing the ...
2
votes
1answer
564 views

How do you convert a regular expression to its disjunctive normal form?

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
1answer
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^*)$.
-1
votes
1answer
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$$ ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
46 views

Semantics of Regex with boundary matchers

The regex /^(abc)$/ matches abc but why not abcdabc, ...
0
votes
0answers
65 views

Empty words in regular languages

Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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, ...
1
vote
2answers
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 ...
5
votes
1answer
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. ...
8
votes
1answer
598 views

Can we convert an NFA to a regular expression of polynomial length?

Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$? In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\...
2
votes
2answers
970 views

Regular expression for even/odd string on alphabet

Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the ...
0
votes
0answers
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", "...
0
votes
1answer
139 views

What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
1
vote
1answer
71 views

Giving a regular expression for a situation of a question

I have the following question regarding a situation given and we are then required to derive a regular expression out of it. What i have to do now i to give a regular expression for this language ...

1 3 4 5 6 7 12