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

learn more… | top users | synonyms (2)

2
votes
2answers
24 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 ...
1
vote
1answer
30 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 ...
0
votes
3answers
119 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?
10
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
41 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
74 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 ...
7
votes
3answers
131 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
40 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. ...
1
vote
1answer
40 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
31 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 ...
-2
votes
2answers
47 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
707 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
66 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
62 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
53 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
36 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
135 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
26 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
35 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
33 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
133 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
26 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
28 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
66 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
24 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?
2
votes
1answer
51 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
31 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
95 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
73 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 ...
2
votes
1answer
31 views

Testing regular expressions algorithmically

Is it possible to test algorithmically whether the language of a given automaton is empty? If I have a language L, could I say that L intersection with the empty set is L?
1
vote
1answer
33 views

Can I write a regular expression or regular grammar for this language?

Let's say I have a formal language, a^n b^n which mean ab,aabb,aaabbb Can I write any regular expression or grammar to create a language like this? I am positive not entirely sure that there is ...
-2
votes
1answer
106 views

Finding a Regular Expression for an Intersection of Two Regular Expressions

Finding a Regular Expression for an Intersection of Two Regular Expressions PAIR of regular expressions is ((ss*)t*) and ((ss*) + (tt*)). How do I find a regular expression that represents the ...
-2
votes
1answer
30 views

how to make a regex that don't accept bab [closed]

hi how to make regex and 'DFA' to don't accept this 'bab' on this alphabet = {a,b} and accept all language except 'bab'
4
votes
0answers
42 views

Direct conversion from regular expression to MSO

A language $L \subseteq \Sigma^*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\{0, \dots, n-1\}, <, (P_a)_{a \in ...
9
votes
3answers
1k views

Can a regular expression be infinite?

I know that languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata ) are equivalent. Also no DFA exists for the language $\{0^n1^n|n \ge 0\}$. ...
2
votes
0answers
52 views

What is the regular expression describing this language?

The language is $\{w \mid \text{$w$ is any string except $11$ and $111$}\}$ where the alphabet is $\{0,1\}$. Drawing the DFA recognizing $\{v \mid \text{$v$ is either $11$ or $111$}\}$, then ...
1
vote
1answer
32 views

How to reduce this regular expression?

I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression? $$b+aaa^*b+abb^*+a$$ I can feel ...
3
votes
1answer
42 views

Star-free decomposition of regular language given by regular expression

I was wondering: is there an algorithm to decompose any regular expression, provided it doesn't use complementation, into one or more regular expressions which don't use Kleene star (only catenation ...
2
votes
1answer
48 views

Converting regular language to regular expression by replacing commas with union

I know that regular languages are those that can be described by regular expressions. For the language {0,1}*, is the corresponding regular expression ...
4
votes
1answer
62 views

What is the complexity of finding a regular expression equivalent to a given DFA?

I had taken a course long ago on complexity theory. I only remember basic things, so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter ...
1
vote
1answer
37 views

Regular expression: b|b equal to b?

I am solving some example exercises in preparation of a Computational Theory examination. In Exercise 2, I am tasked with building an NFA and DFA of the regular expression: $(b|bba)^*a$ My question ...
-1
votes
1answer
57 views

Regular expression in normal (standard) form [closed]

Regular expressions can be reduced to a standard form. A normal form is either 0 or a term of the form $$ \sum_{i \in I} a_i + \sum_{j \in J} n^*_j + \sum_{k \in K} a_k \cdot n^*_k + \sum_{l \in L} ...
3
votes
1answer
60 views

Given regular expression construct regex for the complement language

Disclamer: this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple. Hints are appreciated (as opposed to direct answers). Write an algorithm ...
4
votes
1answer
121 views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
12
votes
2answers
318 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 ...
2
votes
1answer
72 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
135 views

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

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 ...