The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
20 views

Prove regular expression with induction

I need help proving the following regular expression via induction. I have the base case (easy of course) but I'm having a difficult time determining the inductive case. A regular expression over ...
0
votes
1answer
19 views

power + operator for binary

What is the specific definition for power $+$ operator in automata theory? For example, when $x$ is a binary what does it mean that $x = 0^+$. Does it mean that x is a string with at least one $0$?
-1
votes
2answers
33 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to ...
1
vote
1answer
19 views

What is the language recognized by the following deterministic finite-state automaton?

Is the answer: {w : w ∈ {0*,1*} and w contains at least 3 zero} correct?
1
vote
1answer
24 views

Finite Automata for regular expression

I am trying to construct finite automata for this regular expression: Every block consisting of 5 characters need to contain at least two zeros. The regular expression would look sth like this: ...
0
votes
1answer
41 views

Prove that if $L$ is regular, then $f(L)$ is regular too

Prove that if $L$ is regular, then $f(L)$ is regular too. $\Sigma_1$ and $\Sigma_2$ are two arbitrary alphabets, $f$ is a function that maps every symbol of $\Sigma_1$ to an element in $\Sigma_2$, ...
0
votes
0answers
35 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that ...
0
votes
4answers
51 views

If $A^{2x}=4$ what is ${A^{3x}-A^{-3x}\over A^x - A^{-x}}$

If $A^{2x}=4$ and $A > 0$, what is the numerical value of $${A^{3x}-A^{-3x}\over A^x - A^{-x}}$$ Could anyone find the solution and answer? Thanks
1
vote
1answer
30 views

Language with middle third removed

Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...
0
votes
1answer
48 views

Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
1
vote
1answer
22 views

Construction of DFA using an odd bit of language

I am working through a lecture and it constructs a DFA using the language: $$\{w\mid w\textsf{ is any string not in }(ab^+)^\ast\}$$ What does the $(ab^+)$ mean?
0
votes
3answers
31 views

Language of Regular Expression

I'm trying to teach myself Regular expressions for Automata, I'm struggling to work out what the output of $L((1+01)^*)$ would be Would it be the star closure of $\{1,01\}$ or star closure of ...
0
votes
1answer
29 views

How many paths in an NFA

Suppose there is a simple NFA, with 3 states (p,r,q) where p is the start and r is the final. Such that $\delta$ = (p,a,q), (p,b,q), (p,a,r), (p,b,r), (q,a,p), (q,b,p), (q,a,r), (q,b,r), ...
0
votes
1answer
21 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular ...
1
vote
0answers
23 views

Regular Expressions with Repetition

I'm learning about regular expressions and how they represent regular languages of an alphabet. Conceptually, I'm having trouble imagining what a regular expression would look like, representing a ...
0
votes
1answer
25 views

Understanding Kleene star in relation to regular expressions

I have a homework problem for my intro computation class where I have to write a regular expression for an NFA. In order to help understand if my language is correct- I want to post some example ...
0
votes
1answer
33 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: ...
1
vote
0answers
49 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be ...
0
votes
1answer
34 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr ...
1
vote
1answer
12 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
0answers
15 views

Regular expressions divisible by 3

Give a regular expression for the language L over Σ = {a, b}* of words that contain a number of b’s that is evenly divisible by 3. I know that this expression: $(a^∗ba^∗ba^∗b)^∗a^∗$ works for the ...
3
votes
1answer
44 views

Finding a general formula for a regular expression

I need to find the general formula for the regular expression $(S+T)^n$ where $S$ and $T$ are arbitrary regular expressions over a one-letter alphabet and $n$ is an arbitrary natural The general ...
0
votes
1answer
212 views

Prove that $wu=uw$, given that $w^5=u^3$

Suppose $w,u\in\Sigma^*$, $w^5=u^3$, and I need to show that $wu=uw$. I started with $5|w|=3|u|$, but I didn't know how to continue... any suggestions?
1
vote
1answer
33 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
0
votes
0answers
27 views

Regular Expression for a Set of Strings of Even Length

Can the language for the set of even strings be represented by L={ε,aa,ab,ba,bb.....} Isnt Epsilon Odd?
0
votes
1answer
24 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
1
vote
1answer
115 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
-1
votes
1answer
28 views

Regular expression language that describes a graph?

Does anyone know of a regular expression language that can be used to describe a chart with time on the x-axis and price on the y-axis? I would use this language to match regular expressions against ...
0
votes
1answer
18 views

Regular Expression definitions, as a rule, what is always true?

If I have two regular expressions $\sf S$ and $\sf T$, what is always true of these? options: Both $\sf(SS \mid T)^\ast$ and $\sf(TSS)^\ast$ are subsets of $\sf(TSS\mid STS\mid SST)^\ast$ ...
0
votes
0answers
10 views

Subset in a regular expression

Is this true for every two regular expressions G and K? (GG + K)* is a subset of (KGG)* and 2.(KGG)* is also a subset of (GG + K)*
0
votes
0answers
40 views

Prove that $L = \{0^n1^m \mid n ≥ 10, m ≤ 50\}$ is regular and that any subset of it is regular

Question: Let L = {0n1m, n ≥ 10 m ≤ 50}. Prove that this is a regular language and that any subset of it is also regular. Answer or approach: 0 is regular, 1 is regular since any symbol in ∑ is ...
2
votes
0answers
52 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. ...
0
votes
2answers
19 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
1
vote
0answers
46 views

Evaluating $b^*a^*\cap a^*b^*$ to a minimal regular expression

Evaluate to a minimal expression: $b^*a^*\cap a^*b^*$ To me, the only elements to both sets are the empty string, strings containing only $a$, and strings containing only $b$, so isn't the ...
1
vote
1answer
22 views

Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
1
vote
0answers
25 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
0
votes
1answer
15 views

Regular language or not : XAB where X,A belongs to (0,1)+

I am working on a problem a) L1={XAB | X,A belongs to (0,1)^+ and B is Reverse of A} i have to check whether this language is regular or not. I am trying to do ...
0
votes
1answer
28 views

Regular expression for language containing all strings that start and end with different symbols

ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ...
0
votes
1answer
37 views

how to solve equation with epsilon

i am working on a problem for Regular expression and it resulted to this $\epsilon + a+b + aa+ab + ba + bb$ now when i solved it further and reached here $\epsilon + a + b + (a+b)(a+b)$ the ...
1
vote
1answer
24 views

Finding a language accepted by an automaton?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Automata and Finite-state machines. To be specific, I'm ...
1
vote
1answer
33 views

Regular expressions with empty set/empty string

I was wondering if expressions such as: $λ*$ $∅*$ $λ+∅$ $∅λ$ are considered valid expressions. If so, how can I explain them? also if $∅λ$ is valid, does that imply $∅λ∅λ∅λ∅λ∅λ∅λ$ is valid, or ...
0
votes
1answer
53 views

How to determine if a word in $\Sigma^*$ is in a language?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Languages defined by regular expressions. To be ...
0
votes
2answers
143 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
1
vote
2answers
37 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
0answers
40 views

Topology on a free monoid using regular languages.

A free monoid together with arbitrary unions of regular language subsets forms a topological free monoid. Every free monoid homomorphism is continuous with respect to the topology described in 1. ...
2
votes
1answer
33 views

What is the best way of resolving an expression with square roots in denominator?

I was resolving the following question from my textbook: Write each of the following expressions as a single fraction, simplifying your answer where possible: $4 - \frac{1}{\sqrt{12}} + ...
1
vote
1answer
59 views

Regular expression of alternating smaller and bigger digits

How would i go about making a regular expression that alternates between smaller and bigger numbers for an alphabet {0,1,2,3} such as "01032312" or "230102132"
2
votes
3answers
90 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...
0
votes
1answer
31 views

How to convert DFA into RE?

So I am trying to convert this DFA into an Regular Expression. I got an answer but I am not 100% is correct I feel like it is too long. From my understanding, I just need to find the transitions ...
0
votes
1answer
20 views

Find languages L1 and L2, neither of which contains the other, such that (L1* ∪ L2*) = (L1 ∪ L2)*. [closed]

I'm trying solve this question in several ways, but only textbook has not helped me alot.