All Questions

Filter by
Sorted by
Tagged with
0
votes
1answer
16 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 ...
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,...
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, ...
-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 ...
0
votes
1answer
78 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? ...
-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
vote
2answers
58 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
343 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 ...
3
votes
2answers
79 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 ...
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 ...
0
votes
1answer
195 views

Regular expression or automata for language with odd number of 0's and odd number of 1's

Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
2
votes
1answer
40 views

Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

For regular languages $A,B\subseteq\{0,1\}^*$, is $$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$ regular, where $|x|_1$ means the number of appearances of 1 in the word $x$? i need to ...
0
votes
1answer
130 views

Is this concatenation of two FA done right?

$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$ Details: Consider ...
2
votes
2answers
769 views

Language of all strings that has exactly 1 triple b

I am new to automata and learning to make regular expression for languages. But I have been stuck on this one. Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
54 views

Determining initial and final states from FA diagram

I am new to automata. And learning to find concatenation of two FAs. But this one has confused me I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
1
vote
1answer
40 views

In which environment we use NFA(Non Deterministic Finite Automata)?

We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
0
votes
0answers
29 views

Example of a language with linear NFA, but exponential DFA [duplicate]

So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
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 ...
-1
votes
1answer
17 views

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
0
votes
2answers
56 views

Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
0
votes
1answer
39 views

Can this DFA be converted to a regular expression? [duplicate]

I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
0
votes
3answers
213 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$ ...
3
votes
2answers
134 views

DFA that accepts any integer $n$ such that $n \bmod 7 =1$

It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA. Is there smart way to do it without a machine which has memory ...
2
votes
1answer
226 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
2answers
92 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 $...
4
votes
1answer
200 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 ...
1
vote
2answers
355 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
30 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 ...
4
votes
2answers
733 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: ...
1
vote
1answer
72 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 ...
0
votes
1answer
309 views

Do all Regular Expressions describe Regular Languages?

I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent ...
1
vote
1answer
300 views

Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression. On inspecting the given automata, I started deducing the ...
1
vote
1answer
28 views

DFAs that must reach a certain state at least once

I was given this question: Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0. Define the language A⊆Σ* to ...
-1
votes
1answer
98 views

Counter-example to regular expression statement

Show a counter-example to disprove the following statement: If $R1$ and $R2$ are two regular expressions, then $L((R1 \cup R2)^*) = L(R1^* \cup R2^*)$.
0
votes
0answers
139 views

Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
1
vote
1answer
303 views

Whether equivalence of different types of automata is of P-type?

I came across following problem: Which of the following problems is/are P-problems? (I) Equivalence of DFA's (II) Equivalence of NFA (III) Equivalence of regular expressions Now I know I ...
3
votes
1answer
851 views

Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states. However recently came across following text: ...
0
votes
1answer
33 views

How do you get a regex from this DFA? [duplicate]

I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA: And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove ...
1
vote
1answer
60 views

How to find a regular expression

I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules? For example, for the language $L \subset \{ a,b\}^* $ which ...
0
votes
0answers
135 views

Simplification of regular expressions

$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and $(((0^*.1^*)+1)^*(0+1)^*)^*$ I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$ and some identities like $E+RR=R$ and $E.R=R$. I have ...
1
vote
1answer
471 views

Regular Expression converted to NFA

Hello, all, First time poster, here. Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular ...
3
votes
0answers
103 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
1
vote
1answer
141 views

Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?

Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it? Note that alphabet of the given regular expression is binary, i.e. it ...
1
vote
2answers
682 views

Drawing a DFA for a language/regular expression

how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a. My thinking of this is that the regular expression for this is a* c* (...
1
vote
0answers
147 views

Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
2
votes
2answers
151 views

Looking for an “intuitive” regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|...
0
votes
3answers
594 views

Conversion of FA to Regular Expression

If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression ...