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

learn more… | top users | synonyms (2)

6
votes
1answer
50 views

Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching. In ...
0
votes
1answer
40 views

NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ))

I'm currently studying for an upcoming exam in theoretical computer science, but one of the exercises is confusing me: in the exercise sheet it says that the NFA $$M=(\{z_0,z_1,z_2\},\{a,b\},\delta,\{...
-2
votes
0answers
3 views

How to use regular expressions over multiple lines with Python 3.5? [migrated]

If i have the following string = '''This is a multiline string for example purposes more stuff''' I want to use regex to find just the two middle ...
0
votes
1answer
48 views

What is the regular expression of this language? [duplicate]

$\Sigma = \{0, 1\}$ $L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$ $ \#_1(x) = 3 \}$ What is the regular expression of this language? At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $...
-3
votes
0answers
29 views

Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c} [duplicate]

Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c}
0
votes
1answer
24 views

Simple regular expression problem [duplicate]

new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible. We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$...
11
votes
2answers
671 views

Why are regular expressions defined with union, concatenation and star operations?

A regular expresssion is defined recursively as $a$ for some $a \in \Sigma$ is a regular expression, $\varepsilon$ is a regular expression, $\emptyset$ is a regular expression, $(R_1 \cup R_2)$ ...
-2
votes
1answer
31 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
-1
votes
1answer
97 views

Regular expression for language of strings having odd length but even number of $b$'s [duplicate]

I have to draw a finite automaton of a language over $\{a,b\}$ of all strings having odd length and has an even number of $b$s. I already came up with following regular expression $(a+b)((a+b)(a+b))^*...
1
vote
1answer
36 views

Finding the Regular Expression of a language

I'm trying to find a regular expression for the language $$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$ where $n_a(w)$ is the number of $a$s in $w$. I can see that this would generate strings of ...
1
vote
2answers
78 views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
3
votes
1answer
23 views

Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
0
votes
1answer
29 views

Why descriptive power of context-free grammar is greater than regular expression?

Below is a saying from this article. Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the ...
1
vote
1answer
56 views

What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
0
votes
1answer
24 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
-1
votes
1answer
35 views

Does concatenating two empty strings result in an empty string?

I have a question on the multiplication of sets of words as it is defined in Cohen's Intro To Computer Theory. He gives the definition: if S and T are sets of strings of letters, the product of the ...
3
votes
1answer
83 views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
-1
votes
1answer
25 views

Give regular expression on language [duplicate]

What is a regular expression for $L_1=\{a^{2n} b^{3m+1} \mid n \geq 1, m \geq 0\}$?
1
vote
1answer
86 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
29 views

Regular expression for C-style /**/ comments [duplicate]

I am aware that a similar question was already asked here and that the recent question A DFA for recognizing comments is also related but I am not satisfied with the answers. The point is that ...
3
votes
3answers
64 views

Regular expression for a binary string containing even number of 0's

To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it): The regular expression for the above according to me ...
1
vote
1answer
52 views

Regular expression for a finite automaton appears to be wrong

For the following finite state machine: The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the ...
6
votes
1answer
83 views

How do you rank the strings represented by a regular expression?

This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption. I understand format preserving encryption but I don't understand how regular ...
1
vote
1answer
30 views

A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros [duplicate]

This is the automaton I want to find the regular expression for: As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 ...
-2
votes
1answer
56 views

Regular expression of a given language [closed]

Could somebody please confirm if a regular expression of language: $$ L := \{b(ab)^n a^m \mid n, m \geq 0\} $$ is $$\{b, (ab)^* a^*\}? $$ And if not, could somebody please tell me why?
4
votes
1answer
168 views

Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state ...
-1
votes
2answers
64 views

DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in ...
3
votes
2answers
69 views

Compare regex in programming languages with regular expression from automata/formal language?

I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages. These two differ not just ...
1
vote
3answers
81 views

Regular Expression simplification

Does $(0 + 10^{*}1)^{*}$ simplify to the following language: Set of all binary strings with even number of ones. In specific, does the * inside the brackets get evaluated first or the outer * gets ...
2
votes
1answer
112 views

Is it legal to draw an NFA with fewer nodes than what I normally see?

Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?
1
vote
1answer
39 views

regular expression to accept all strings other than one containing ads or adlib [closed]

My intention is to select only those packages whose name do not contain adlib or ads. But if i add *adlib* and *ads* it selects all packages containing the ...
0
votes
1answer
55 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can "see"...
2
votes
2answers
78 views

DFA to regular expression how to deal with 'sink state'

Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink ...
2
votes
1answer
45 views

Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear. Now to go from that NFA to the complement of the NFA, since I can't just flip accept ...
1
vote
3answers
163 views

Is the empty string of even length?

There is this example of regular expressions: $$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$ From that I understand the empty string is valid as a string of even length. Is this true?
11
votes
3answers
2k views

Regular languages that can't be expressed with only 2 regex operations

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular ...
0
votes
1answer
55 views

How do I derive a regular grammars from this regular expression? [closed]

How do I derive a regular grammars from this regular expression? (a or b)*ba(ba)* I'm stuck with the last part so ...
0
votes
3answers
154 views

Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

This is for formal-language-style regular expression and not about Unix-style regular expression. I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings ...
9
votes
3answers
459 views

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

We can form DFA accepting binary numbers divisible by $n$. For example DFA accepting binary numbers divisible by 2 can be formed as follows: Similarly DFA accepting binary numbers divisible by 3 ...
4
votes
1answer
68 views

Implementing regular expression matching using Brzozowski derivatives

I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. ...
2
votes
1answer
49 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ ...
-3
votes
1answer
38 views

Step by step method for generating Regular Expressions for languages [duplicate]

I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where: $L= \{w \in \{0, 1\}^{\ast} \mid \text{length of } w ...
-1
votes
2answers
63 views

Is the set of regular expressions over an alphabet equal to Σ*?

Are the following two sets equal? One the set of regular expression over an alphabet, and the other set is the set of all strings which can be generated by using the symbols of an alphabet(Σ*)?
4
votes
2answers
728 views

Is a single string enough to prove regular expressions inequivalent?

Which of the following regular expressions generate a language that is different from the rest? (a+b)$^*$a(a+b)$^*$(a+b)$^*$ b$^*$ab$^*$a(a+b)$^*$ (a+b)$^*$ab$^*$ab$^*$ b$^*$ a(...
1
vote
1answer
83 views

Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,…,z)*} [duplicate]

The question I'm working from is: Prove whether or not a finite automation exists that recognises the following language: B = {ww | w ∈ {a,b,c,...,z)*} EDIT So I believe this is a non-regular ...
4
votes
2answers
84 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 ...
0
votes
0answers
13 views

regular expression identities and NFAs [duplicate]

I have these two problems about regular expressions, can you help me? 1) Prove (ab)∗a = a(ba)∗. I already proved this using induction and the definition of the kleene star * but I want to prove it ...
0
votes
2answers
66 views

Regular Expression representing the following language

I am having trouble understanding how to write a regular expression for the set of words that contain at least two b's and at least two a's, where the alphabet is {a,b}. I understand that set of ...
0
votes
3answers
43 views

Difference in having * inside vs outside of brackets for NFA

If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for ...
2
votes
1answer
145 views

∅-free regular expressions?

This is a question involving regular expressions for regular languages. I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a ...