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

learn more… | top users | synonyms (2)

-1
votes
1answer
34 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
47 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
22 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
40 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
57 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
68 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
votes
0answers
10 views

How do I represent the set of strings of odd length in regular expression form over the alphabet Σ = {a, b} [duplicate]

I know that a{aa}* would give you all of the odd length strings for a, but the fact that there are two elements in the alphabet are throwing me off a bit.
1
vote
1answer
26 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
55 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
133 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
49 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
64 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
80 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
2answers
110 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
49 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
54 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
40 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
150 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
52 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
121 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
295 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
50 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
47 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
36 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
58 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
725 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
77 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
65 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
63 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
40 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 ...
0
votes
0answers
14 views

Regex matching the language [duplicate]

A couple homework problems that I've been working on, hoping I can get it done right. Can anyone confirm if my line of reasoning and regex is correct? L = { $w \in $ {$x, y$}* | $w$ contains a ...
1
vote
1answer
39 views

Finding regular expression for a language with more substring of one type than from another

Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110. I tried to figure out what would be the finite automata but I'm not to ...
1
vote
1answer
458 views

What is the minimum pumping length of the following languages?

How to determine the minimum pumping length of union of two languages? How do I proceed after determining the individual pumping lengths? 0*1+0+1* U 10*1 - Here the minimum pumping length of the ...
0
votes
1answer
27 views

Converting sets into regular expressions

In my book: The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba. The set ...
-2
votes
1answer
33 views

Regular Expression for the given DFA [duplicate]

Hi, what should be the regular expression for this language ? My guess was r = (a ∗ a(a + b) ∗ (a + b) + (a ∗ b + c))(a + b ∗ ) ∗ But the arrow from C to B is making it tough . If it was B to C ...
2
votes
2answers
83 views

String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...
-3
votes
1answer
27 views

Regular expression for do not contain

What is regular expression for language that does not contain $1110$? It is easy to guess for language that contains. The shortest way I know is go through DFA. Is there a better way?
3
votes
1answer
103 views

Kleene plus in Thompson's construction

Is there a direct way to represent Kleene plus(+) using Thompson's construction algorithm? When I studied Thompson's construction I learned how to transform concatenation, union and kleene star of ...
0
votes
0answers
28 views

Convert Dfa to RE [duplicate]

I want to covert this DFA to RE: I converted and this is my result: 1*+1*2+21*, but I test it and give wrong result. This dfa describe "any strings(lambda) but not contain 22". Please help me ...
-2
votes
1answer
35 views

Regular language subsets [duplicate]

If $L_{1} \subseteq L_{2}$ and $ L_{2}$ is regular, does it follow that $L_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we ...
3
votes
1answer
148 views

How to prove closure property of regular languages using regular expressions?

I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular ...
1
vote
1answer
85 views

Set of all Languages [closed]

Sorry if the Question sounds a little trivial. Let A* be the set of all languages over A={a,b}. Then A can be written as {aUb}* which is a regular expression.So this is the set of all ...