# Questions tagged [regular-expressions]

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

724 questions
Filter by
Sorted by
Tagged with
15 views

### I cant figure out which regular experesion solves my problem [duplicate]

The language L=a binary number with even number of digits that doesnt have 2 consecutive zeroes. What is the regular expression that can search those words and how what is your thought process when ...
29 views

### Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
25 views

### Can any language be expressed by regular expression?

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &...
18 views

### Structural induction proofs for regular expression [closed]

Let $RE$ be the set of regular expressions over the alphabet {a,b} How do I go about proving the following using structural induction For each r $\in$ $RE$ there is a $r'$ in $RE$ such that $\epsilon$ ...
22 views

### Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
22 views

### Can a non-regular language have a regular grammar?

Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now: S -> 1 | 0 | ε Since it ...
50 views

### Regular grammar for language that does not contain "abab"

I tried this : $V = \{S,A,B\}$ and $T = \{a,b\}$. $S \rightarrow aS | \epsilon | abaAS | BS$ $A \rightarrow a | aA$ $B \rightarrow bB | \epsilon$ Any thoughts/objections?
29 views

### Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
554 views

### Regular Expressions - What is difference between a+ and a⁺

I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
38 views

### conversion of regular expression to automata

I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$ My first solution looks like this: I would like to ...
28 views

### Regular expression for words without two equal consecutive letters

I need to find a regular expression for the language over $\{a,b,c\}$ consisting of all words in which no two consecutive letters are the same. For example, $abacbabca$ is in the language, while $abbc$...
39 views

### Are Nondeterministic Finite Automata not allowed 'sink-states'?

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
28 views

### How to interpret the regular expression 0*10|01(01)*?

I'm having some trouble understanding the regular expression $0^*10|01(01)^*$. The expression matches strings like $00010$. But for some reason, I wasn't able to find a string that matches the $(01)^*$...
38 views

### set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
56 views

### If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
29 views

### Convert regex pattern to LL1 parser

Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain ...
24 views

### Regular expression for all a* except aa?

I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable: a aaa aaaa aaaaa ... It's for part of the below DFA
71 views

### I have found an example where regular expression is not closed under concatenation. Where am I wrong?

$a^n$ is a regular expression. $b^n$ is a regular expression. their concatenation is $a^nb^n$ which is not a regular expression.
63 views

25 views

### DFA and RE find out the language. Please can you explain?

Find the regular expression describing following languages over alphabet {0, 1}*. ...
151 views

### What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
45 views

### Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
25 views

### Is non-equivalence of regular expressions with union, concatenation and squaring NEXPTIME-hard?

On wikipedia, page about EXPSPACE it says An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions ...
34 views

### Is my regular expression correct for this question?

IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
43 views

### High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
58 views

### Are the regular expressions equivalent?

Is the following equivalence true? $$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$ I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
47 views

### Are this languages can be represented by regular expressions?

The set of all words with the same number of 0’s and 1’s. The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s. I guess first one is NO. Second one seems ...
27 views

### How do I solve regular expression expansion when I have "+" sign?

For example, I am given this and my output is: 11+11* = 11, 1, 11, 111, 1111, ...... Since + means or sign, my logic is: 11 appears once or more Then I work on solving 11* Is it perfect? Thanks.
30 views

### Does finding a reversal of a regular expression by automata need automata to be a DFA?

If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?
73 views

### Which of the following languages can be represented by regular expressions?

The set of all words contained in $\{0,1\}^*$ that have an even number of 0’s and an odd number of 1’s. I came to discover that it is possible but not sure how. Can anyone express it in a regular ...
46 views

### How to carry out expansion in regular expression problems like ((0*10)*)?

I have been given some problems like: Determine if each of the following strings belongs to the corresponding regular language. i. ‘10100010’ and L((0*10)*). iv. ‘011100101’ and L(01*10*(11*0)*) I ...
29 views

### Minimal state DFAs for a regular expression of length $n$

I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
72 views

96 views

### Proving $(a + ab)^*a = a(a + ba)^*$

Need to prove $(a + ab)^*a = a(a + ba)^*$ by using regular algebra. Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use ...
34 views

### Regular identity proof or disproof

I have to prove or disprove the following identities: $(RS+R)^*RS=(RR^*S)^*$ $(R+S)^*S=(R^*S)^*$ $S(RS+S)^*R=RR^*S(RR^*S)^*$ So what I tried: Not same because LHS cannot generate $\epsilon$ while ...
53 views

### Describe regular expression

I am learning about regular expression, and trying to describe a regular expression for the language L $\qquad L = \{a^i b^j c^k \mid i+j = k\}$ What is the right approach and how to describe a ...
149 views

### Regex for strings with even number of 1's and number of 0's divisible by 5

I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as $0$ multiple of five times and odd $1$'s $0$ multiple of ...
32 views

### Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$

Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$ So basically we have the language $L=\{11,011,110,0011,1100\ldots\}$. I find the ...
19 views

### Regular set corresponding to regular language

I have just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds ...
81 views

### Can a non-regular language $L$ have a non regular $L^*$?

I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
139 views

### How many languages are described by a regular expression?

How many languages can a Regular Expression describe is it only one or infinite? I have tried to google it but i haven't found any answer? I know that a Regular Expression describes a Regular Language?...