Questions tagged [regular-expressions]

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

526 questions
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
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 ...
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 ...
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). ...
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$$ ...
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 ...
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 ...
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)?
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?
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 ...
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 ...
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\}$.
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 ...
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* ...
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 ...
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 ...