Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
574 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
94 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
65 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
772 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
71 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
370 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
45 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
207 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
113 views

Does there exist a finite automaton for the given language?

The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$: $L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $...
2
votes
1answer
100 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) $\...
3
votes
1answer
35 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
80 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 ...
5
votes
1answer
468 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
72 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
140 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: ...
3
votes
2answers
667 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 ...
6
votes
3answers
2k views

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression ...
1
vote
2answers
741 views

Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA

As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA. It should not generate more strings than the upper bound n if it contains ...
1
vote
1answer
27 views

Minimum number of letters

I have an assignment that I have to do and the question is Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}. Im not looking for the answer but rather some direction. I ...
2
votes
1answer
80 views

Is the language $a^nwa^n$ regular?

The given description of language is: $\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$ I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can ...
0
votes
1answer
85 views

Explanation for the regular expression for the set of all string over the alphabet {0,1}

Why does set of all strings over the alphabet {0,1} is represented by (0+1)*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+...
1
vote
1answer
2k views

How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states. I have this difficult DFA i need help converting to RE: using STATE ELIMINATION ...
1
vote
0answers
830 views

How can I find worst time complexity for a Regular Expression problem?

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution? One way is to perhaps use The Master Method for ...
1
vote
1answer
32 views

Number of strings accepted by this regular expression

This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices. If a regular ...
0
votes
3answers
235 views

Concatenation of language to itself zero times

I was solving this question: Which of the following statement(s) is/are false? $L^0=\{\epsilon\}$ $|L^0|=0$ The answer given was None. That is, none of these statements are false and ...
1
vote
1answer
47 views

“Or” in regular expressions

I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it. One basic problem I wanted to solve was ...
-1
votes
1answer
38 views

Regularity under set difference

Let L be a regular language. Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$ How do I prove it is wrong?
5
votes
2answers
3k views

Simplification of regular expression

I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems. How would one approach simplifying the following regular expression: ...
2
votes
1answer
172 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
29 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 ...
0
votes
0answers
85 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 ...
2
votes
1answer
58 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 ...
-2
votes
1answer
970 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
269 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
45 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 ...
0
votes
0answers
26 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
133 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
603 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
110 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
648 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
82 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
75 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
3answers
6k views

DFA for Strings with third symbol from RHS as 1

How can we make a DFA for given condition in title from alphabets {0,1} (binary). What can be the regular expression for this? My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'...
0
votes
0answers
307 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
936 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
122 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
1k 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 ...
2
votes
1answer
412 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 ...
4
votes
1answer
728 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
468 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 ...

1
3 4
5
6 7
13