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

learn more… | top users | synonyms (2)

10
votes
2answers
541 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)$ ...
-4
votes
0answers
24 views

Prove or disprove (r*)* ≡ r* [duplicate]

$(r$1* )* $≡ r$1* My intuition says that these two are equivalent in the strings they will accept/generate. I am not sure how to prove it if such is the case.
-1
votes
0answers
17 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 ...
-3
votes
0answers
13 views

Help with Regular expressions [duplicate]

language of all those strings whose length is Odd, but contain even number of b’s defined over alphabet set {a,b}. i tried bb((a+b)(a+b))* is this correct? plz help
-1
votes
1answer
95 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 ...
1
vote
1answer
34 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
69 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
21 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 ...
-3
votes
0answers
12 views
0
votes
1answer
28 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 ...
-3
votes
0answers
29 views

How do I produce a regex from an automaton?

I'm confused as to whether it is required that I hit the final state or not. So far, I have (011)*(0011)*00 I don't know how to account for the path 0101011 because after that sequence, then there ...
1
vote
1answer
30 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 ...
1
vote
1answer
23 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
57 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
82 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
28 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
60 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
50 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
72 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
27 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
148 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
60 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
67 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
111 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
54 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 ...
2
votes
2answers
62 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
44 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
153 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
53 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
140 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
348 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
57 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
37 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
62 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
727 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$^*$ ...
1
vote
1answer
80 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
66 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
65 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
41 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
142 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 ...
2
votes
1answer
27 views

How is (0|1|…|n) handled as a DFA?

How is n-times regex alternation operation, e.g. (0|1|...|n), handled in a DFA (MYT algorithm)? Here are the rules for the MYT also (Converting Regular Expressions to NFAs ): ...
-2
votes
2answers
37 views

Alternative for regular expression

Could the following be considered as an alternate regular expression for regex $a(aa)^*$? $a^k$ where $k$ is odd. Could the following be considered as an alternate regular expression for regex ...