Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
304 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
3answers
4k views

DFA for Strings with third symbol from RHS as 1

How can we make a DFA for given condition in title from alphabets {0,1} (binary). What can be the regular expression for this? My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'...
0
votes
1answer
13 views

Lexicographic Order of Expression [Automata Theory]

what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order? I'm confused and I really want to clear my concepts so I can proceed further
0
votes
3answers
201 views

Does the distributive property apply to regular expressions?

Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does $$ (q_1a+q_2b)c=q_1ac+q_2bc $$ hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$? Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ ...
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
21 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
1
vote
1answer
61 views

Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
1
vote
1answer
186 views

Proving that $ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$?

How would I prove that these two regexes are equal to one another? $$ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$ I'm permitted to use the following regular expression identities.
1
vote
2answers
93 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition $$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$ But I dont really know how to apply this information to check whether or not a grammar ...
2
votes
1answer
212 views

How do I convert the following GNFA to regular expression?

Here is a GNFA I made from an NFA. I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
0
votes
1answer
23 views

Need help understanding regular expressions

I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
1
vote
1answer
66 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
1answer
873 views

How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states. I have this difficult DFA i need help converting to RE: using STATE ELIMINATION ...
-2
votes
1answer
37 views

Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
2
votes
1answer
575 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 ...
0
votes
0answers
44 views

Regex to match number ranges less than a certain number

I'm trying to write some code to match numbers below certain bounds. I would much appreciate nay help somebody could give, I'm pretty lost with this one... NB. I've checked the forums and can find ...
0
votes
0answers
27 views

Converting DFA to RE [duplicate]

I have been trying to solve this problem. Convert the DFA to a regular expression. I extracted these following equation. $q_1 = q_2a$ $q_2 = q_1a + (a+b)q_3$ $q_3 = q_1b + q_2a $ Also,the ...
-2
votes
2answers
2k 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
34 views

Kleene Star regex question, sed behavior? [closed]

Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*". Does anyone know why this regex is not being matched against the ...
0
votes
1answer
43 views

find derivation trees for CFG

I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below. I want to know how many possible derivation trees are there from this grammar. $$\begin{align}V_n&=\{expr,term,...
3
votes
2answers
98 views

Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression. I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
2
votes
1answer
23 views

Why $P$ cannot have NULL string in Arden's Theorem?

Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what ...
0
votes
1answer
29 views

Product of Lexical Specification

I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc. The options are: ...
0
votes
0answers
18 views

regular expression with kleene closure [duplicate]

my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...} in that case i don't understand the meaning what (R*)* means
0
votes
1answer
23 views

Counting number of states from a regular expression

Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A ...
2
votes
1answer
88 views

Finding a regular expression of a language

Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
0
votes
2answers
91 views

Does there exist a finite automaton for the given language?

The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$: $L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $...
1
vote
1answer
24 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
0
votes
0answers
49 views

How generate regular expression on the alphabet {a,b}?

How can I write a regular expression that denotes language on the alphabet {a,b} of the strings that do not present "b" consecutive and the total number of "a" is multiple of three?.
2
votes
1answer
10 views

Regular expression notation clarification

For the alphabet $Σ$={a,b,c} I was wondering how you would say: T that has elements from Σ, so could be T=a, T=bc I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure ...
2
votes
2answers
148 views

What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
0
votes
0answers
42 views

What is the best algorithm known to learn the regular expression from a set of positive examples?

I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I ...
2
votes
0answers
22 views

Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs? I understand the difference between them, and can follow the ...
5
votes
1answer
15k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
0
votes
2answers
8k 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 ...
1
vote
1answer
78 views

DFA multiple accepting states to Regular expression

I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states. If I understand this DFA correctly, it recognises:...
-1
votes
2answers
66 views

Regular Expression For The Language Σ = {0,1}

I have an language of Σ = {0,1} and need to find the the regular expression of: Set of strings that have no pairs of consecutive zeros Set of strings that contain ...
3
votes
1answer
50 views

Is there an algorithm to overapproximate a context free grammar by a regular expression?

I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
2
votes
0answers
30 views

Transform Double Metaphone code into regex

I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please ...
0
votes
1answer
65 views

Regular Expression: L= {w | every even position of w is '1'}

I am trying to solve a regular expression of binary string where every even position is a '1' I've solved this for an odd position: (1(0+1))*(1+ε) How would it look like for an even position then? ...
0
votes
3answers
89 views

Define a finite automaton accepting the language below [duplicate]

$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$. About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
12
votes
1answer
12k views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
2
votes
1answer
22 views

Modelling regex replacement via a DFA

I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis: ...
2
votes
2answers
56 views

Is intersection used in regular expression?

As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?
3
votes
2answers
36 views

Interpretation of this regular expression: (1*0*)*

Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )? For example, 110011001100 is part of this language set, but 1100100010 isn't? Or can the values of the ...
0
votes
0answers
18 views

Arden theorem with 3 input [duplicate]

I have just started learning Arden's theorem to convert finite automata but I am stuck on its execution when we have 3 inputs. Because I am not able to simplify any equation to have only 2 inputs ...
0
votes
1answer
47 views

Prove that the language is not regular [duplicate]

Prove that the following language $Σ = \{1\}$ is not regular. $L$ = $\{w | |w| = k$, where $k$ is a prime number}. How should one go about proving this? Should I use pumping lemma for this?
-1
votes
1answer
40 views

Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?

Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
1
vote
1answer
23 views

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-2
votes
1answer
12 views

Regular expressions for some languages [duplicate]

Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00. $\{a^n b^m : n ≥ 4, m ≥ 3\}$. Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.