# Questions tagged [regular-expressions]

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

617 questions
Filter by
Sorted by
Tagged with
21 views

### Regular expressions accepted by programming languages but are not regular [duplicate]

The below definition of Regular Language is given in Wikipedia. In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
36 views

### a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
35 views

### How to apply Arden's theory to determine a regular expression

If $P=ab$ and $Q=a^*$, how do I use Arden's theorem to determine the regular expression $R$. I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
40 views

### Can a regular expression be any string from the language described by it? [closed]

Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
29 views

### Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
60 views

### Extracting regex submatch boundaries without backtracking

I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
42 views

### Regular expressions

I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback. The question is: ...
61 views

### Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
91 views

### CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $S \to Α Β S$ $A \to S$ $B \to a B b$
37 views

### Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
32 views

### validation of a pumping lemma proof for regular languages

I have the following regular expression: Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT I was just wondering, because $L$ is made up of a union of ...
21 views

### What is Pumping length for Union of Regular languages?

This is an exam question. For E = {a,b}. let us consider the regular language $L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$ Which one of the following can be a pumping length (the constant ...
25 views

### I can't seem to convert a NFA to a regex. What am I doing wrong? [duplicate]

I have the following diagram : I try to remove state 3: Now I do this: What do I do now to get my regular expression? I'm stuck.
238 views

### What is the computational complexity of “real-life” regular expressions?

Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), ...
26 views

32 views

### Is this a valid DFA for (a|b)*abb?

I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried: It seems valid to me but I'm ...
12 views

### How to write regular expression [duplicate]

The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's Can you guys tell me what is the correct answer for this ?
15 views

### Regex vs line by line read efficiency - general concept question

Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...
43 views

### Regular grammars

I am fairly new to automata, regular expressions and regular grammar. I am struggling to understand how to define the regular expression (abc)* into one or several regular grammar expressions. ...
52 views

### McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA

I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter....
115 views

### Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state: if x = s + xr then x = sr*, with $s,r\in$ Regular ...
92 views

### Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing that the ...
46 views

### Are these REs equivalent?

I have to implement a compiler for a given language as part of an assignment. The language is kept simple enough such that it can be fully expressed through REs. My question lies with two of the REs ...
62 views

### regex of three repeating number

I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but ...
66 views

### Generating regular expressions not containing abc

Let sigma = {a,b,c}. How do I generate a language L that does not containg abc? Any guidance is appreciated!
25 views

### How to describe the languages of these regular expressions in plain English?

This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck. The question is Give English description of the languages ...
67 views

### Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
33 views

### How to write a regular expression that excludes certain strings? [duplicate]

It's a homework problem. Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb. My idea was: construct a regex that matches ...
170 views

### Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
48 views

### Prove the equivalence between regular expressions (cb*c+cb*b)* and (cc)*+(cc)*(cb)(b+c)*

I need to prove the equivalence of the following regular expressions: (cb*c+cb*b)* (cc)*+(cc)*(cb)(b+c)* using the following equivalence rules: • (1) (E + F) + G = E + (F + G) • (2) E + F = F + E ...
133 views

### Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...
### Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring. She wrote ...