Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
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
0answers
23 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 ...
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 ...
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
2answers
95 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 ...
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)∗...
-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 ...
0
votes
0answers
46 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 ...
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,...
2
votes
1answer
24 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 ...
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 ...
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 ...
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
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
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
23 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 ...
1
vote
1answer
85 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
70 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
92 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 ...
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
57 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
20 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
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$.
-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
182 views

Are regular expressions a*a and aa* equivalent?

Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is ...
0
votes
0answers
38 views

construct regular expression for a language [duplicate]

I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ...
1
vote
2answers
56 views

DFA & RE from descriptive definition of given regular language

I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them. Some strings ...
2
votes
2answers
321 views

DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
0
votes
0answers
47 views

Returning all the combinations of a string using regex

Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches? For example, if the string is ...
4
votes
2answers
68 views

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
3
votes
2answers
78 views

Regular expression for binary words with 1 in the middle

Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$ I'm having trouble finding a ...
0
votes
1answer
41 views

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$ I think this languages is regular. I write regular expression: $(1 + 2 + 0) ^ {*} (11 + ...
1
vote
2answers
107 views

Is the language of words that contain a square regular or context-free? [duplicate]

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
72 views

State-elimination on FSA, after epsilon-removal construction

I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression. But there are already some epsilon ...
2
votes
1answer
45 views

How to use homomophism in closure proofs?

I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
1
vote
1answer
45 views

Maximum number of words in deterministic finished automata with k-states [closed]

I have exercise: We have a given finished deterministic automata. It has 5 states and is based on the alphabet {a, b, c}. It can create n different words (we assume that n < inf). What maximum ...
1
vote
1answer
43 views

Difference between methods of converting from finite state machine to regular expression

I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine: ...
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: ...
1
vote
1answer
59 views

Why is this not recognized by a DFA?

I am still confused over my professor's explanation on why this problem is not a DFA. The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA My professor explained it as ...