Questions about regular expressions, a formalism to describe regular languages.
-3
votes
1answer
81 views
THE QUESTION IS ABOUT ARTIFICIAL INTELLIGENCE [on hold]
Right now I am posting questions,answers and comments ON MY PC-LAPTOP} computer using my wits which is normally needed by a computer.postings are for the main site of theoretical computer science....
1
vote
1answer
18 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 ...
2
votes
0answers
16 views
Which transducer models replacement in regex?
I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order.
For example: ABC => CAB, which, with ...
0
votes
0answers
16 views
Derivatives of Extended Regular Expressions
I'm trying to formulate the derivatives of a few extended regular expressions:
$[c_1, c_2, . . . , c_n]$ -- a range of characters
$r^{n..}$ -- r repeated n or more times (where n ≥ 0)
$r^{n..m}$ -...
0
votes
2answers
26 views
How to deal with character set in regular expression?
In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
1
vote
1answer
34 views
Regex for at least three 1's and at most four 0's
The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's.
I've come up with a method that enumerate every possible number of 0's:
$$111^{+}+0111^{+}+1^{+}...
0
votes
0answers
14 views
Look-behind assertion of variable length as formal regex
Background
Some time ago, I needed a look-behind assertion and learnt that Perl does not (naturally) support such constructions. I know Perl as the language for doing regular expressions ...
1
vote
1answer
33 views
How to Apply Elementary Axioms from Kleene Star to an Inequality
Axioms For *
\begin{align}
1 + aa^* &\leq a^* \\
1 + a^*a &\leq a^* \\
b + ax &\leq x \to a^*b \leq x \\
b + xa &\leq x \to ba^* \leq x \\
\end{align}
Elementary Results
\begin{...
1
vote
1answer
42 views
If $L$ is a regular language, then $s(L)$ is also regular
...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.
For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.
My ...
0
votes
1answer
41 views
Different iterations of regular expressions
A four-part question dealing with formal languages and regular expressions:
How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How ...
0
votes
1answer
67 views
Trying to simplify a particular regular expression
The question is as follows
$$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$
But I am unable to solve this regex expression. My answer is as follows:
\begin{alignat*}{2}
(a^* + (ba)^* )^...
0
votes
2answers
62 views
Does there exists a finite automata for the given language?
The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as:
$L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
2
votes
1answer
34 views
Proving formula for derivative of Kleene star
Prove that for any symbol $a$ and regular expression $r$ it is true that:
$$\partial a(r^* ) = \partial .a(r)(r^* )$$
My attempt:
Induction on regular expression $r$
Base cases:
1) $\...
0
votes
0answers
30 views
regular language for NFA [duplicate]
I'm trying to find the w-regular language of this NBA. In 'Principle of Model Checking' - Book there's an algorithm for this problem:
1. Take the NBA as NFA and create the regular language to get from ...
0
votes
0answers
48 views
Regular expressions - Do i need the $*$ inside $()^*$-brackets?
Do i need the $*$ after the first $B$ in this regular expression $(B^* + C)^*$ ?
Do i need the $+$ after the first $B$ in this $\omega$-regular expression $(B^+ + C)^\omega$
Stated differently: Is $(...
3
votes
1answer
30 views
Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?
I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this?
I've tried the pumping lemma but I don't think it applies here. I've also tried ...
1
vote
1answer
41 views
Proving equivalency of regular expressions
x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)
I am looking for a method that is applicable to prove such questions.
I know that proof ...
4
votes
1answer
49 views
Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression
Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?
The way I solved this problem is to first convert the NFA ...
2
votes
1answer
64 views
Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?
Consider the following set constructed with a regular Kleene-star operation:
$$
\{10^n \mid n\geq1\}^*
$$
Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but ...
2
votes
1answer
26 views
Regular expression for capturing a “C-style” string
I have started to learn automata theory and languages. I am new to regular expressions.
As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
2
votes
2answers
127 views
Is DFA and Regular Expression equivalent?
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?
If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
6
votes
3answers
1k views
How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression
...
1
vote
2answers
131 views
Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA
As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.
It should not generate more strings than the upper bound n if it contains ...
1
vote
1answer
26 views
Minimum number of letters
I have an assignment that I have to do and the question is
Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}.
Im not looking for the answer but rather some direction. I ...
0
votes
0answers
29 views
Is Pushdown Automata “equivalent” to RegEx with balancing group?
From my textbook, NFA, DFA, and Regular Grammar are "equivalent" in the sense that they can be transformed into each other.
I learned from the Internet that:
Nondeterministic Pushdown Automata is "...
2
votes
1answer
45 views
Is the language $a^nwa^n$ regular?
The given description of language is:
$\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$
I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can ...
0
votes
1answer
24 views
Explanation for the regular expression for the set of all string over the alphabet {0,1}
Why does set of all strings over the alphabet {0,1} is represented by (0+1)*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+...
0
votes
1answer
278 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
...
0
votes
0answers
30 views
How can I find worst time complexity for a Regular Expression problem?
I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution?
One way is to perhaps use The Master Method for ...
0
votes
0answers
38 views
A list of regex and a list of strings
Given a list A of regex of size n and a list B of strings of size m, you need to output the regex that corresponds to at least one string in B. One way to do is by looping which gives an O(nm). Is ...
1
vote
1answer
29 views
Number of strings accepted by this regular expression
This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.
If a regular ...
0
votes
3answers
74 views
Concatenation of language to itself zero times
I was solving this question:
Which of the following statement(s) is/are false?
$L^0=\{\epsilon\}$
$|L^0|=0$
The answer given was None. That is, none of these statements are false and ...
1
vote
1answer
40 views
“Or” in regular expressions
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.
One basic problem I wanted to solve was ...
-1
votes
1answer
29 views
Regularity under set difference
Let L be a regular language.
Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$
How do I prove it is wrong?
4
votes
2answers
95 views
Simplification of regular expression
I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems.
How would one approach simplifying the following regular expression:
...
2
votes
1answer
48 views
Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?
(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)
Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language?
This question ...
1
vote
0answers
14 views
Pseudo-random regex-searchable function
Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:
$f$ is efficiently ...
0
votes
0answers
41 views
Validating attempt on NFA to Regular Expression
So i tried turning the following NFA into a GNFA (first attempt).
Please don't ask why i chose to do such a complex NFA on my first try, i just like the challenge i guess?
ab is the concatenation of ...
2
votes
1answer
36 views
Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?
If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪
(rs)*.
I think this is not true. And I believe this would always be true :
(r ∪ s)* = r* ∪ s*
I wanted to clarify this ...
0
votes
0answers
43 views
Can the state removal (GNFA) method be directly applied to an NFA to get its equivalent regular expression?
Lots of lecture handouts or other materials I have found on the web say we can convert any DFA to an equivalent regular expression by converting it to a GNFA(Generalized Non-deterministic Finite ...
0
votes
0answers
17 views
Trouble coming up with an expression to describe a DFA [duplicate]
This is a DFA that describes a language over {a,b} that only accepts a string if the number of a's in the string is not divisible by 3. I'm having difficulty coming up with an expression for it, I'm ...
-1
votes
1answer
44 views
What is the regular expression for strings containing at least one a and at least one b? [duplicate]
$L = \{w \in \{a, b, c\}^*\mid w\text{ contains at least one }a\text{ and at least one }b\}$.
what's the proper regular expression for the following language?
0
votes
1answer
33 views
All finite languages can be decribed using a regular expression? [duplicate]
I have a question.
All finite languages can be decribed using a regular expression?
3
votes
1answer
44 views
Generating all words of length $n$ avoiding $A^2$ and $B^3$
I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing?
I ...
0
votes
0answers
24 views
NFA to RE question [duplicate]
Converting the following NFA to Regular Expression.
Quick question:
Do I have to add a new initial state as Q1 is accepting an incoming edge with 0+1 from itself?
Method used:
State elimination ...
1
vote
1answer
44 views
Regular expression that have the same number of 0 and 1
I'm doing some Automata Theory exercises through a book and I'm trying to solve the exercise below but I cant figure out how to solve it.
Could I get a hint on how to construct a regular expression ...
-1
votes
1answer
68 views
Regular expression of a language over {a,b} which does not contain substring bbb [duplicate]
I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
5
votes
1answer
54 views
Relative succinctness of NFAs and regular expressions
What is known about the succintness of NFAs, relative to regular expressions?
In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the ...
0
votes
1answer
187 views
Regex for divisibility by 123 in binary strings
Is there a regex that checks for divisibility by 123 in binary strings?
This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative ...
2
votes
1answer
70 views
Is there a way to find a simple regular expression for this language?
Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is ...
