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

learn more… | top users | synonyms (2)

3
votes
1answer
56 views

For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?

Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA. Is it ...
1
vote
1answer
28 views

Difference between the two regular expression

I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba*b)*. However I found the ...
1
vote
0answers
45 views

Converting this DFA to RE using the Brzozowski Algebraic Method [on hold]

Hello people, I'm trying to convert this DFA to RE using the Brzozowski Algebraic Method. (DFA created with JFlap) My Attempt Write down equations R1 = bR1 + aR2 + ɛ R2 = bR2 + aR3 ...
2
votes
1answer
106 views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
0
votes
1answer
30 views

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

I have doubt ! Problem is what is language of repeat(L) = {ww | w ∊ L} ? I know it {ww | w ∊ (a,b)*} is context sensitive language. here , what is meant by "repeat(L)" ? Can you explain it ? ...
3
votes
1answer
26 views

Arden's lemma applicability on context free grammars

The Arden's lemma states that there exists a solution to the equation between regular expressions r = sr + t, with r unknown, and it is s*t. I went through some other topics on the forum and I always ...
1
vote
1answer
54 views

How do I find a regular expression for a particular language?

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
2
votes
1answer
18 views

Pumping lemma regular language can't be pumped

Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that ...
0
votes
1answer
40 views

Regular expression - every b preceded and followed by an even number of a's

I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s. I think the regular expression should ...
-3
votes
0answers
22 views

Why is this regular expression equivalent to this automaton? [duplicate]

Given this automaton $A$: Why is $\qquad L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$? Please explain in a descriptive way step by step.
0
votes
1answer
46 views

What's the difference between $a^*+b^*$ and $(a+b)^*$?

What's the difference between the regular expressions $a^*+b^*$ and $(a+b)^*$. Do both of these generate the same language? I was told in a lecture that $(a+b)^*$ will generate string concatenation of ...
-1
votes
1answer
50 views

Regular expression for words in a language where each letter appears at least once

What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once? Acceptable words: $ abc, cba, cbcbcba, abbbcaabb$ ...
0
votes
0answers
25 views

Find language (and/or regular expression for automaton) [duplicate]

How do I go about finding a language recognized by the following automaton? And is it possible to find a corresponding regular expression? I've read some posts about the same issue here on CS.SE but ...
1
vote
1answer
39 views

Defining if a language is regular [duplicate]

$L_4 = \{ w | w \text{ does not contain symbol a immediately followed by symbol b} \} $ where: $ \Sigma = \{ a, b, c \} $ So far I believe I have a defined regular grammar for this language, however ...
-1
votes
1answer
46 views

Regular expression of a language over {a,b,c} which does not contain substring bbb

I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the ...
1
vote
1answer
68 views

Converting Regular expression to DFA by building syntax tree

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
0
votes
1answer
59 views

Regular Expression from Context Free Grammar [duplicate]

The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular ...
2
votes
1answer
64 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
0
votes
2answers
45 views

How to get the intersection of two regular languages?

I was trying to figure out the value of the following expression. (0 | 1)*00 ∩ (0 | 1)*01 I tried drawing DFAs for(0 | 1)*00 ...
-1
votes
1answer
57 views

Why the given lexical specification will not process the following strings?

I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question. Here ...
0
votes
1answer
32 views

Why a language specified by a regular expression is not a complement of a given language?

I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct. Here is the question. For any ...
4
votes
4answers
138 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
2
votes
1answer
85 views

Is this method of proving non-regularity is equivalent to pumping lemma?

I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed ...
0
votes
2answers
149 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
4
votes
1answer
56 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
0
votes
1answer
75 views

What is the minimal number of states for the DFA?

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex? $1$ $2$ $4$ $5$ ...
2
votes
2answers
33 views

How is regular expression law: $\emptyset L = L\emptyset = \emptyset$ correct?

I am taking a course on Automaton where I faced the algebraic laws of regular expressions. First two were ok: $\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language ...
-2
votes
1answer
101 views

Thompson's Construction Algorithm produces a different NFA

My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, ...
1
vote
1answer
48 views

Converting a NFA to its equivalent regular expression

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions. I have the following NFA: I'm using the state ...
2
votes
1answer
76 views

Can DFA with output (definition?) match expressiveness of NFA with unique output?

For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of ...
2
votes
1answer
26 views

Simplying this regular expression

I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal: $ (\epsilon + 0^*1^+0)^* = \epsilon + (0+1)^*10 $ here ...
1
vote
2answers
41 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
-2
votes
1answer
154 views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset ...
1
vote
1answer
226 views

Regular expression for language with even number of 0's and 1's [duplicate]

Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s? If we only require an even number of $0$'s, the language ...
-1
votes
2answers
668 views

Regular Expression for even-odd language of string

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of ...
5
votes
0answers
64 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
2
votes
0answers
61 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
1answer
58 views

Regular Expressions with at least 2 0's and at most 1

I think the answer should be: $(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon)$ But I am not sure if this is the right answer. Can someone explain the correct answer? And if it is ...
6
votes
2answers
302 views

Decidability of “Is this regular expression prefix-free?”

Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it ...
0
votes
0answers
29 views

$L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular [duplicate]

Use the Pumping Lemma to show that $L$ is not regular: $$ L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ...
-2
votes
2answers
60 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
6
votes
3answers
348 views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
4
votes
1answer
111 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
0
votes
0answers
21 views

Learning a regex from string examples? [duplicate]

Given some strings, is there some algorithm (and program that implement such an algorithm) that can create a regex which matches some of the given strings and not the other given strings? Note that ...
3
votes
1answer
118 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and ...
0
votes
0answers
59 views

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
0
votes
0answers
21 views

Representing lookbehind and lookahead in FSMs based off regexes [duplicate]

As part of an assignment, I have to write regexes matching lists of rules and then make state machines representing those regexes. Heavy use of negative lookbehinds and lookaheads is essential in one ...
2
votes
1answer
80 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
0
votes
2answers
31 views

Can anyone help me understand the matches to this regular expression?

My professor gave us this pattern "/[aeiou]+[1234567890]*[a-z]?/" and I'm trying to find matches in "ae12abc r2d2 a1steaksauce". The resulting matches the professor gave us are ae12a, a1s, eak, auc, ...
5
votes
1answer
69 views

When a regexp is not a Regular Expression?

Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a ...