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

learn more… | top users | synonyms (2)

0
votes
0answers
1 view

How to get the intersection of two regular languages?

I was trying to figure out the value of the following expression. (0 | 1)*00 ∩ (0 | 1)*01 I tried drawing (0 | 1)*00 and ...
-1
votes
1answer
53 views

Why the given lexical specification will not process the following strings?

I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question. Here ...
0
votes
1answer
28 views

Why a language specified by a regular expression is not a complement of a given language?

I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct. Here is the question. For any ...
4
votes
3answers
104 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
2
votes
1answer
83 views

Is this method of proving non-regularity is equivalent to pumping lemma?

I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed ...
-1
votes
0answers
20 views

regular expression for string [duplicate]

What will be the regular expression of string containing no. Of 0s and 1s odd over the set{0,1}* It should accept all the strings generated by odd no. Of 0s and 1s combination For exampke if i say ...
0
votes
2answers
96 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
4
votes
1answer
43 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
0
votes
1answer
52 views

What is the minimal number of states for the DFA?

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex? $1$ $2$ $4$ $5$ ...
2
votes
2answers
30 views

How is regular expression law: $\emptyset L = L\emptyset = \emptyset$ correct?

I am taking a course on Automaton where I faced the algebraic laws of regular expressions. First two were ok: $\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language ...
-2
votes
1answer
72 views

Thompson's Construction Algorithm produces a different NFA

My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, ...
1
vote
1answer
40 views

Converting a NFA to its equivalent regular expression

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions. I have the following NFA: I'm using the state ...
2
votes
1answer
66 views

Can DFA with output (definition?) match expressiveness of NFA with unique output?

For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of ...
2
votes
1answer
24 views

Simplying this regular expression

I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal: $ (\epsilon + 0^*1^+0)^* = \epsilon + (0+1)^*10 $ here ...
1
vote
2answers
40 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
-2
votes
1answer
90 views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset ...
1
vote
1answer
97 views

Regular expression for language with even number of 0's and 1's [duplicate]

Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s? If we only require an even number of $0$'s, the language ...
-1
votes
2answers
227 views

Regular Expression for even-odd language of string

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of ...
5
votes
0answers
55 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
2
votes
0answers
59 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
1answer
54 views

Regular Expressions with at least 2 0's and at most 1

I think the answer should be: $(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon)$ But I am not sure if this is the right answer. Can someone explain the correct answer? And if it is ...
6
votes
2answers
281 views

Decidability of “Is this regular expression prefix-free?”

Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it ...
0
votes
0answers
28 views

$L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular [duplicate]

Use the Pumping Lemma to show that $L$ is not regular: $$ L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ...
-2
votes
2answers
58 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 ...
5
votes
3answers
186 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
108 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
107 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
55 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^*)^*$ ?
0
votes
0answers
20 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
74 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
50 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
56 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
68 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
59 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
111 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
1k 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
22 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
106 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
63 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
128 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
61 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
82 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
93 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
47 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
106 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
60 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
53 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
108 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 ...