Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
27 views

What is the logical reasoning behind Arden's Theorem proof of unique solution?

Here is the proof for Arden's Theorem assertion that R=QP* is the unique (only solution) to R=Q+RP. My question is: what is the logical reasoning to prove that any equation is the unique (only ...
3
votes
1answer
21 views

Converting DFA to RE with Arden's Rule

So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting ...
3
votes
1answer
101 views

Regular expression for strings not starting with 10

How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
-1
votes
0answers
24 views

Show that this language L' is regular [duplicate]

I'm not even sure where to begin with this. The language given is: L' = { x∈Σ* | ∃y∈Σ*, |x|=|y| and xy ∈ L}. Basically, L' consists of the first halves of the strings in L, where L is a regular ...
3
votes
1answer
50 views

Prove the equivalence of regular expressions

I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated. Suppose there exists regular expressions R, S and T. ...
0
votes
0answers
13 views

Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...
0
votes
0answers
21 views

Regex Questions?

I need to match all words having two adjacent vowels that differ. I did this /\b(?=\w*([aeiou])(?!\1)[aeiou])\w+/ but I am not allowed to use the ?! and it needs to be done in as few characters as ...
0
votes
2answers
12 views

Regular expression containing lambda

What is the meaning of lambda here: $$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$. I know that lambda is used in the context of NFA? Let's suppose we break down the expression ...
0
votes
0answers
18 views

Is this language regular or not regular {(a* union b)a } intersection {a*b*} is a regular language [duplicate]

Is {(a* ∪ b)b } intersection {a* b* } a regular language?
4
votes
1answer
58 views

Can every regular expression be written as sum of products?

I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages. To prove this, I decided to proceed as ...
1
vote
0answers
26 views

Is ASM a regular language?

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
-1
votes
0answers
16 views

Regular expression required [duplicate]

Give a regular expression for L={a^n b^m |n>=1,m>=1,nm>=3} I tried something like this: a(a)* . bbb(b)*
1
vote
1answer
46 views

Different application of Arden's theorem leads to different answers

So, I have to solve for the following set of equations $q_1$ = $q_1$a + $q_2$b + $\epsilon$ $q_2$ = $q_1$a + $q_2$b + $q_3$a $q_3$ = $q_2$a There are two ways to do this. I did this ...
0
votes
0answers
21 views

What exactly is “pattern matching”?

I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions. But is there a precise definition? In particular, it seems that it has to do with ...
1
vote
0answers
34 views

Regular expressions for set of all strings on alphabet $\{a, b\}$

I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$): $(a^*+bb^*)^*$ $(a^*b+b^*a)^*$ $(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$ I want to ...
0
votes
1answer
25 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
0
votes
0answers
27 views

What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?

I was trying to make a regular grammar for resource identifier described as follows: Consider the set of all strings over the alphabet $\{ a, b, / , . \}$ that represent an RI (resource ...
-2
votes
2answers
62 views

$L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language

Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
3
votes
3answers
252 views

Regular Expression with at least one a, even number of b

I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language ...
5
votes
3answers
880 views

How to determine minimum word length of regular language

Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$? A straightforward example: Let's ...
0
votes
0answers
8 views

Binary string regex problem, starts with a 1 and has an even number of 0s [duplicate]

I am trying to make a regex expression that is: A binary string that starts with a 1, and has an even number of 0s. I tried, 1(1*01*01*)*, but it misses the case where it is 11. How would I go about ...
3
votes
3answers
122 views

Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
4
votes
1answer
37 views

Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...
0
votes
1answer
19 views

Regular Expressions to accept strings where every two successive 0s are followed by a 1

How do I define a Regular Expression for the language L = {w|every two successive 0s are followed by a 1} ? I don't have any idea on how to even approach this problem, primarily because it says "...
0
votes
1answer
27 views

Regular expression for containing 010 as a subword

I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand. I managed to solve the following question: ...
3
votes
1answer
29 views

Regular expressions with cycles

A knob is used to select one of three positions A, B, C. The knob can never be turned from A to C, or from C to A, without spending at least one second in position B. The initial position of the knob ...
-1
votes
0answers
16 views

Help in converting NFA to regular expression [duplicate]

Hi I don't understand how to convert NFA to regular expression in the question below. Can someone help me to solve and understand example below
0
votes
0answers
26 views

Proving that the language of regular expressions is not regular

Prove that the language consisting of all valid regular expressions is not regular. I am approaching this using the Myhill-Nerode Theorem as follows: I am trying to find a pairwise distinguishable ...
0
votes
0answers
22 views

Minimal DFA for “$n$th character from the right is $a$” [duplicate]

I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$: $$ (a|b|c)^*a(a|b|c)^{n-1}. $$ The exercise asks for the number ...
2
votes
1answer
48 views

Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
4
votes
2answers
60 views

Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
0
votes
1answer
57 views

The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular [duplicate]

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)
0
votes
0answers
35 views

Regular expression for set of strings with no two consecutive 1's? [duplicate]

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's. I'm also wondering if there is a pattern that could be extended to ...
3
votes
1answer
116 views

How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
-1
votes
1answer
46 views

Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...
2
votes
1answer
53 views

Arithmetic operators and regex

Let $L$ be the language over the alphabet $\{0, 1, 2, 3, (,), +, -, *, /\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$. 2 - ...
2
votes
1answer
39 views

Algorithm to Minimize a Regular Expression

I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this? For ...
0
votes
0answers
36 views

How to prove that L(G) is not regular by contradicting the pumping lemma?

I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
2
votes
1answer
316 views

show that if L is a regular, then drop(L) is a regular

I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof. I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I ...
1
vote
1answer
25 views

I need help in this regural expression exercises [closed]

Write a regular expression for the language of words over $\{0,1,2\}$ satisfying the following requirements: The word has length at least 3. The last symbol is 2. The second to last symbol ...
0
votes
2answers
47 views

No FSM/Regex exists for this language right?

The language is this: $L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$ This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, ...
2
votes
0answers
29 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
5
votes
0answers
95 views

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
0
votes
1answer
26 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
26 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
43 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
115 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
366 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
27 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
46 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 ...