Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
42 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
161 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 ...
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 ...
0
votes
0answers
31 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 ...
0
votes
2answers
58 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 ...
1
vote
0answers
167 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
2answers
64 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$$ ...
0
votes
1answer
48 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
1answer
177 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 ...
-1
votes
1answer
17 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)?
0
votes
1answer
39 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?
3
votes
2answers
150 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 ...
4
votes
2answers
831 views

How is $\emptyset^* = \{\epsilon\}$?

I know that $\emptyset$ is a an empty language, i.e. language containing no string. A law involving empty language is: $\emptyset L = L\emptyset = \emptyset$ It correctly states that we cannot ...
1
vote
1answer
60 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\}$.
2
votes
0answers
83 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 ...
2
votes
2answers
5k views

how did they get this answer for the words that don't have bba and abb?

I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb. and the answer was a*(baa*)*b+b*(a*ab)*a* ...
0
votes
1answer
44 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
2answers
53 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
257 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
56 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{...
0
votes
1answer
158 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)^* )^...
2
votes
1answer
3k views

Regex: Any pair of zeros is before any pair of ones

Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is: $$(0+10)^*(00)(1+01)^*(11)(0+10)^*(1+01)^...
2
votes
1answer
68 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) $\...
2
votes
1answer
3k views

Regular expression for words over $\{0,1\}$ containing at least one 1

I had an exam on Theory of Computation, and one of the questions was to write down a regular expression for the language over $\{0,1\}$ consisting of all words containing at least one 1. My answer was:...
4
votes
1answer
225 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 ...
3
votes
1answer
32 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
62 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 ...
0
votes
1answer
15k views

Converting NFA to regular expression [duplicate]

Here is the regular expression I made for it This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( (a|(b^*a))ba^...
2
votes
1answer
70 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
77 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: ...
17
votes
1answer
285 views

Regular expressions with backreferences over unary alphabet

Setting: regular expressions with backreferences unary language (1-symbol alphabet) Is the following problem decidable in this setting: Given a regular expression with backreferences, does it ...
3
votes
2answers
439 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
383 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
63 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
50 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
0answers
431 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 ...
2
votes
1answer
225 views

What is language of repeat(L) = {ww | w ∊ L}? [closed]

What is language of repeat(L) = {ww | w ∊ L} ? My try: I know it {ww | w ∊ (a,b)*} is context sensitive language. Here , what is meant by "repeat(L)" ? Can you explain it ? It is not a homework ...
1
vote
1answer
30 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
112 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
41 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
35 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?
4
votes
2answers
945 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
105 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
19 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
45 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 ...
3
votes
1answer
569 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
0
votes
0answers
72 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
164 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 \...