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

learn more… | top users | synonyms (2)

-2
votes
2answers
35 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
4
votes
2answers
44 views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
4
votes
1answer
89 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
0
votes
0answers
20 views

Learning a regex from string examples? [duplicate]

Given some strings, is there some algorithm (and program that implement such an algorithm) that can create a regex which matches some of the given strings and not the other given strings? Note that ...
3
votes
1answer
98 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and ...
0
votes
0answers
44 views

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
-3
votes
0answers
59 views

Regular expression question

I have the following question in my homework but I'm not sure what the answer is. I'd appreciate it if someone could help me. The question is as follows: The language of regular expression ...
0
votes
0answers
19 views

Representing lookbehind and lookahead in FSMs based off regexes [duplicate]

As part of an assignment, I have to write regexes matching lists of rules and then make state machines representing those regexes. Heavy use of negative lookbehinds and lookaheads is essential in one ...
2
votes
1answer
57 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
0
votes
2answers
30 views

Can anyone help me understand the matches to this regular expression?

My professor gave us this pattern "/[aeiou]+[1234567890]*[a-z]?/" and I'm trying to find matches in "ae12abc r2d2 a1steaksauce". The resulting matches the professor gave us are ae12a, a1s, eak, auc, ...
5
votes
1answer
38 views

When a regexp is not a Regular Expression?

Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a ...
1
vote
1answer
55 views

Understanding Regular Grammers

I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with ...
1
vote
1answer
53 views

Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...
1
vote
1answer
50 views

minimum number of states for the regular expression

Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^*$$ I was able to create a DFA with 8 states, but the place I saw the question ...
-1
votes
1answer
97 views

Pumping Lemma Proof by contradiction [duplicate]

So, hi guys! I have a language which I am trying to prove that it is not regular using the Pumping Lemma. I am pretty new into the lemma so I would appreciate any help.The language is $$L = \{w | w ...
7
votes
3answers
574 views

Why is the Kleene star operator also called the Kleene 'closure' operator?

I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept. I don't understand why the ...
-1
votes
1answer
18 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 .. ...
3
votes
3answers
101 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 ...
1
vote
1answer
52 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
108 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
43 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 ...
0
votes
1answer
72 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
72 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
45 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
71 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
52 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
48 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
94 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 ...
14
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
204 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 ...
0
votes
1answer
518 views

Converting NFA to regular expression [duplicate]

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
276 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
95 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
116 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
490 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 ...
4
votes
1answer
2k 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 $q_2$ is: If we first ...
-2
votes
1answer
81 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
56 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
78 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
216 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
85 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
68 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
90 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
165 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
116 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
115 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
77 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
208 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
150 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: ...