Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

2
votes
1answer
17 views

Help with figuring out if MAX(L) is a CF language

We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as: $MAX(L)$ = {$w_1 \in L $|...
-1
votes
0answers
17 views

How to precisely know whether a language is regular ? , a regular expression can be generated for it ? , as well as dfa? [duplicate]

I feel difficulty in finding whether a language is regular and also is regular expression can be generated ?? Please anyone let me know about all the possible cases. This will help me very much..
1
vote
1answer
36 views

Can the difference of a non-regular and a regular language be regular?

I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises: If $L_2,L_3$...
2
votes
2answers
42 views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$ If i'm not mistaken the condition is the same as ...
2
votes
1answer
42 views

Construct a DFA from the regular expression (a)*+(aab)*

I've broken down the expression into two simpler DFAs but right now I'm stuck. I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
12 views

Proving a language comprised of 2 languages is regular(with suffix and prefix)

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular: $$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
17 views

Proving a language comprised of 2 languages is regular

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it. The question: $L_1$ and $L_2$ are regular languages over the ...
5
votes
1answer
45 views

Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How ...
1
vote
0answers
21 views

How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
1
vote
1answer
28 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
1
vote
1answer
50 views

Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it. As per my understanding non deterministic context free grammar is a context free grammar ...
1
vote
0answers
25 views

Tree languages regular

Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2. To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular. So it's ...
3
votes
3answers
81 views

CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this: S→A|B A→aE|aA|EA B→bE|bB|EB E→aEbE|bEaE|Λ ...
2
votes
2answers
31 views

Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular

I have been looking around for a good source to answer the following question. Have read a few different sources but have not found the answer I was looking for. The question is: Give an example ...
2
votes
1answer
61 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^*$, which their length is a product of 3 (meaning their length is divisible by 3). ...
0
votes
1answer
37 views

Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$ [duplicate]

$L_1^*∪L_2^*⊆(L_1∪L_2)^*$ I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of ...
0
votes
0answers
29 views

Understanding handle, viable prefix and valid item in the context of LR(0) and LR(1) items

Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as ...
1
vote
1answer
58 views

When will SLR(1) parser fail but CLR(1) will not

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont: Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
1
vote
0answers
56 views

What is the word “madness” doing in the first chapter's title of Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman?

The chapter's title is "Automata: The Methods and the Madness". This title came along in the second edition and remains in the third edition. In the first edition, the the second chapter's title is "...
0
votes
0answers
13 views

building turing machine for busy beaverproblem

I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
0
votes
0answers
26 views

Using Nerode theorem to prove that the following languages are non-regular

I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked. The problem is to prove the ...
2
votes
3answers
60 views

proving L1* ∪ L2* ⊆ (L1∪L2)*

x∈ L1* ∪ L2* ⇔ x∈ L1* ∨ x ∈L2* ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)* Is it enough to prove it this way?
2
votes
1answer
56 views

In what sense a type of parser is less power than the other?

I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
1
vote
1answer
39 views

MSO (Monadic second-order logic) Logic On Words

Let L be a language over $\Sigma = \{a,b,c\}$ that contains all words, where the length $|w|_b$ (number of all b's) has remainder 1 if divided by 3. MSO logic over words are definded as follow: I ...
1
vote
1answer
69 views

I have trouble translating Turing machine language, can you help me break down language notation to English?

My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing ...
0
votes
0answers
14 views

Connection of relation between valid item and viable prefix with canonical collection

I was trying to understand connection between different concepts of parsers and how those are followed in actual parsing steps. I came across following statement while reading LR parsers: An item ...
0
votes
1answer
42 views

Dana Angluin's L* algorithm - Hypothesis inconsistent

is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent? So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
0
votes
2answers
49 views

Prove that the following language is regular [duplicate]

Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA. Prove that the following language is regular, by making an appropriate NFA for it: 𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
1
vote
0answers
26 views

Computational power of quantum finite automata

I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
-1
votes
2answers
59 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 ...
-1
votes
1answer
88 views

Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }

$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$ I have trouble about this PDA. Anybody can help me about draw this PDA?
2
votes
1answer
41 views

The order of ε-transitions in NFA

I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want ...
3
votes
1answer
289 views

reduction from 3-SAT to Subset Sum problem

How to reduce 3-SAT to subset sum problem?
-1
votes
1answer
72 views

Backtracking in DFA [closed]

Is it true that backtracking is allowed in deterministic finite automaton (as mentioned in many comparisons between DFA and NDFA)? If yes, how is it possible when transition in DFA is to a single ...
0
votes
1answer
63 views

Limitations of DFA [duplicate]

In this link it is mentioned: A DFA is not powerful enough to recognize many context-free languages because a DFA can't count. But counting is not enough -- consider a language of ...
0
votes
1answer
49 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? ...
1
vote
1answer
39 views

Simple property of DFAs

Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)? Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
1
vote
1answer
33 views

How to check if DFA is actually a correct model of the intended system?

Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind? For example, say I have DFA ...
1
vote
1answer
49 views

Why are those very similar languages in a different complexity class?

i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
0answers
30 views

is this given language in class P? [duplicate]

i was wondering: is this language in class P? $NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$ explanation: a ...
0
votes
0answers
19 views

How to prove this language is not context-free language by pumping lemma? [duplicate]

Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?
0
votes
0answers
41 views

prove that the language is not context free language

Prove that the language $\{a^i b^j c^k $ $|$ $i>j>k \geq 0\}$ is non context free language without using the pumping lemma. we could use some helpful facts to solve the question: $A$ is a ...
0
votes
1answer
47 views

Operations making non-context-free languages regular [closed]

If $A$ is a non-context free language, is $A^*$ a regular language? If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?
0
votes
0answers
63 views

How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]

Let $L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets. $L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
2
votes
1answer
54 views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
2
votes
1answer
383 views

Some basic questions on halt and move in Turing machines

Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write ...
1
vote
1answer
50 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
0
votes
0answers
12 views

Howcome the string “b” is accepted by this nondeterministic finite state automata per the given solution?

Am I correct that the given solution is implying that the string with a single b, "b" is accepted by this NFSA? If so, I don't understand how "b" can end up in the accepting state.
1
vote
1answer
70 views

Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there ...
1
vote
3answers
67 views

Is it possible to define a DFA for the language of words having exactly one double letter? [closed]

Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example, $baaba$ has exactly one double letter, but $baaaba$ has two double letters. Suggested answer ...