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

learn more… | top users | synonyms (2)

0
votes
1answer
13 views

Regular expression syntax

am a little confused by regular expression to convert to NFAs. am actually test using http://www.regexr.com/ but some of regular expression like a*+ab is that mean (a*)+ is that correct .. ...
2
votes
3answers
75 views

Was there an attempt to make reusable regular expressions?

In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating ...
0
votes
1answer
27 views

Regex: Any pair of zeros is before any pair of ones

Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is: ...
2
votes
1answer
85 views

regular expression for binary language has at least one 1

So I had an exam in the subject "Theory Of Computation" and one of the questions was to write down a regular expression of a binary language that has at least one (1) , my answer was : 0* 1 0* (0* 1 ...
0
votes
1answer
31 views

Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)

How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are ...
-1
votes
0answers
16 views

Theorems to prove non-regularity without pumping lemma [duplicate]

What are some theorems that can be used to show the existence of non-regular languages without using the pumping lemma?
0
votes
1answer
61 views

Regular expression for a binary number that includes “10” and has an odd number of 0's

I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't ...
-1
votes
1answer
50 views

Converting DFA to regular expression [duplicate]

I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it. In my steps, I think there is a bug because I do not know ...
-3
votes
1answer
38 views

The meaning of $*$ in regular expressions

I'm designing a Turing machine that decides a language denoted by a regular expression. Let's say this expression is $a^*bbc^*$. Does this machine accept the string $bb$ since $a^*$ and $c^*$ can have ...
-1
votes
1answer
36 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
-1
votes
1answer
40 views

Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
3
votes
2answers
42 views

Finding out if languages involving counting and modulo operations are regular

I am having trouble with the regularity of the two following languages: i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$ ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$ To clarify this is stating that the ...
1
vote
2answers
84 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
13
votes
6answers
2k views

What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had ...
10
votes
2answers
178 views

Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was. Can you solve the following problem in polynomial time or is ...
-1
votes
1answer
102 views

Converting NFA to regular expression

Here is the regular expression I made for it This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( ...
9
votes
1answer
258 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
1
vote
2answers
60 views

How to write regular expression excluding certain pattern aba from albhabet set {a,b}? [duplicate]

Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite? Is there any generic way to write a regular ...
0
votes
2answers
93 views

Describe in English the pattern in the following regular expressions

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
1
vote
0answers
27 views

Describe in English the pattern in the following regular expressions [duplicate]

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
2
votes
6answers
364 views

Regular expression (ab U a)* to NFA with two states (Sipser)?

In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA. And then the text ends with: "In ...
2
votes
1answer
385 views

Convert DFA to Regular Expression

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The q_2 state is eliminated first. The provided solution to eliminate q2 is: ...
-2
votes
1answer
63 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
2
votes
1answer
47 views

Is it possible to repeat a wildcard in regex?

.{5} would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character." The immediate way that ...
0
votes
1answer
59 views

Convert regular expression to Automaton

I'm trying to construct a finite-state automaton from the following regular expression: $$ (a|ba)(a|ba)^*(b|ab)^* $$ I know that from $$ (a|ba) $$ the automaton should look something like this: ...
0
votes
3answers
163 views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
0
votes
1answer
80 views

Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions. Conditions: ...
0
votes
2answers
60 views

Recognizing a language given a Automata

I'm trying to figure out which language can be recognized in this automaton According to wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted ...
2
votes
3answers
88 views

What is the regular expression to the given language?

I can't really find out, how can the following given Language be written down with regular expressions $ L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \} $ I had some guesses, but I don't know ...
4
votes
1answer
149 views

Complexity of bitwise AND operation on bit string regular expressions

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
0
votes
2answers
99 views

regular expression in license plates

I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The ...
1
vote
1answer
84 views

regular expression: sum of positive fixed point decimal numbers [closed]

I need help with this exercise. Indicate the regular expression for the following Languages. Explain your expression in one sentence and indicate the basis form of the alphabet. Indicate also every ...
3
votes
1answer
73 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in ...
5
votes
1answer
173 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
0
votes
2answers
132 views

Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this: ...
3
votes
1answer
210 views

Regular expression to show that all strings contain each symbol atleast once

I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so ...
0
votes
2answers
79 views

find a regular expression and FA that each define $L_1 \cap L_2$

I am trying to find a regular expression and finite automaton that each define $L_1 \cap L_2$, where $L_1 = (ab^*)^*$ and $L_2 = ...
0
votes
1answer
55 views

Why $R\circ\emptyset$ is not always equal to $\emptyset$

I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is ...
0
votes
1answer
94 views

About trap states when converting DFA to regular expression

If we were to have a trap state in a DFA and we are converting it to a regular expression, how exactly would I incorporate that into the regex? Let's say our language only accepts a*, and my DFA has a ...
0
votes
1answer
256 views

how did they get this answer for the words that don't have bba and abb?

I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb. and the answer was a*(baa*)*b+b*(a*ab)*a* ...
5
votes
2answers
82 views

Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
0
votes
0answers
72 views

Proving a regular expression is correct [duplicate]

I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979). Specifically, I'm unsure how to justify that my regular ...
1
vote
3answers
67 views

Precedence in regular expressions

I'm having trouble finding the language represented by the following: (AA|BB)* Should the expression be read as... ( A (A|B) B ) * or... ( (AA) | (BB) )* If that isn't clear, should this produce ...
4
votes
2answers
810 views

Difference between 1* + 0* and (1 + 0)*

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?
15
votes
1answer
418 views

Is regex golf NP-Complete?

As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ...
0
votes
2answers
85 views

Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example: Assume the following regular expression: ...
1
vote
1answer
467 views

Redundant States During Removal of Null-Moves (Regular Expression to DFA)

I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask. Coming to the question, my old coursebook ...
1
vote
1answer
164 views

Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s

Like the title says, we have the alphabet $\Sigma = \{a,b,c\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two ...
1
vote
0answers
29 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(a*a*)?(a*a*) and I convert it to a grammar: G ::= A B A ::= ...
0
votes
3answers
737 views

NFA or DFA for strings the contain exactly twice substring ab?

Given the language with alphabet: $\{a, b, c\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody ...