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.

learn more… | top users | synonyms

-2
votes
2answers
31 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
-3
votes
1answer
24 views

Why is this sequence not acceptable for this DFA?

Why is the sequence 1100101 not acceptable for this DFA? Is it because once it reaches the final state 'q3' it can't go back to 'q1'?
-1
votes
2answers
47 views

How to prove that these two languages are regular, or not regular?

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
4
votes
2answers
37 views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
1
vote
2answers
47 views

Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
0
votes
1answer
33 views

DFA that recognizes 0 in every odd position

I had a question that asked for the DFA that accepts the following language: {w | every odd position of w is a 0 } Should this DFA accept the empty string, since ...
-3
votes
1answer
59 views

Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
-2
votes
1answer
21 views

Constructing Epsilon-closures

I am recently learning about automaton and I was confused at an exercise that was given to me. In the lecture, we were given this exercise: Given a FA with transitions $$\begin{array}{c|ccc} ...
0
votes
1answer
29 views

Which cellular automata rules are suitable for randomizing an input sequence?

S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random ...
2
votes
3answers
218 views

Why do all non-empty ω-regular languages have periodic members?

I was learning about Büchi Automata and couldn't understand a part where they were describing "Non-empty $\omega$-regular languages contain periodic strings" Let $A$ be a Büchi automaton ...
4
votes
2answers
677 views

Can a Language be determined by its kleene closure?

Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from ...
0
votes
1answer
36 views

Prove that Language is not Regular using closure(s)

I'm having a really tough time trying to comprehend proofs via closure and pumping lemma. None of the examples I can find are similar to the one's im looking to prove. Can anyone explain if I'm ...
1
vote
0answers
23 views

Number of states of finite automata [duplicate]

Prove that for each $n>0$, a language $L_n$ exists where $L_n$ is recognizable by an NFA that has $n$ states, and If $L_n=K_1 \cup \dots \cup K_k$, for regular languages $K_i$, then at least ...
0
votes
2answers
34 views
2
votes
0answers
86 views

DFA for a regular language

I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
1
vote
1answer
36 views

Construction of a counter automaton for the complement of the palindromes

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = ...
-3
votes
1answer
33 views

A finite automaton accept no string

How can a finite automaton over(0,1) doesn't accept any string? I only can think of s->a->q->F Where the final state F is empty set. Is that true ...
0
votes
1answer
35 views

designing a DFA and the reverse of it

There is a theorem that says if a language is regular, it's reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?
0
votes
0answers
31 views

Designing a turing machine to determine if there is path from two vertices in a directed graph or not

I'm self studying automata and I'm in chapter 7 of Sipser book. I want to design a diagram for a Turing machine that shows if there is path from s to t in a directed graph. My tape is like this: ...
1
vote
1answer
38 views

Is a k counter automata a special kind of PDA?

I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special ...
4
votes
2answers
55 views

Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
2
votes
1answer
33 views

Omega-Language to Büchi automaton

I'm currently preparing a presentation about LTL and a book says that the language $L = (a(a \cup b))^\omega$ cannot be described by any LTL (or FO) formula which is understandable but how does the ...
0
votes
1answer
38 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
-2
votes
1answer
39 views

Construction of an NFA knowing only the equivalence classes and some examples of L [closed]

For a certain language $L \subseteq \{a, b\}^∗$, IL has exactly four equivalence classes. They are $[\lambda]$, $[a]$, $[ab]$, and $[b]$. It is also true that the three strings $a$, $aa$, and ...
3
votes
2answers
74 views

When states that are not accepting states become accepting states in NFA, what happens?

It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some ...
0
votes
1answer
40 views

Making a finite automata

How can I make a finite automaton which does not end in string ab. With the alphabet a,b I made 3 states. For the first one it is accepting states and thus accept the empty string. So here is a ...
1
vote
2answers
20 views

Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
0
votes
3answers
90 views

Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.
2
votes
0answers
25 views

When is the best time to include an ε-transitions in a NFA state diagram?

While doing my NFA homework in my automata class, I feel like I'm not taking advantage of the ε-transitions I'm learning about. I can solve problems without using it. It's not like I really need it, ...
-1
votes
1answer
60 views

Union of two finite automata?

How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look ...
4
votes
2answers
177 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
0
votes
1answer
29 views

Turing machines with a finite number of states

In a class on Turing machines, the lecturer said that the language for a machine with 100 states is both recognizable and decidable. How can we infer this just from the number of states in the ...
0
votes
2answers
72 views

How does an NFA use epsilon transitions?

In the picture I've provided, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the epsilon jump at q0. If a 0 is entered, does the system move to both q0 AND ...
3
votes
5answers
123 views

is it possible to minimize pushdown automata?

is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
1
vote
2answers
31 views

Is this language regular [duplicate]

Let L is a regular language then is L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L} regular? Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield ...
0
votes
1answer
79 views

Getting minimum DFA for regular expression (11)*+(111)*

(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too) The language corresponding to given regex seems to ...
1
vote
1answer
44 views

Regular and not Regular Grammar

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as S -> abS|a and G2 = ({S,S1,S2,},{a,b},S,P2) S -> S1ab S1 -> S1ab|S2 S2 -> a ...
0
votes
1answer
48 views

Regular Grammar and Regular Language [closed]

From Wikipedia, Regular Language All finite languages are regular. and Also Regular Grammar, is a way to describe the Regular Language Right regular grammar (also called right linear ...
1
vote
1answer
29 views

Is it possible to “unshift” onto a queue using this theoretical “queue automaton”?

I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. ...
0
votes
2answers
53 views

How to make a Post Machine for $a^nb^n$?

I have tried to make a Post machine for that all words of the form $a^nb^n$ by the following steps. add a marker '#' read first 'a' read next 'a's and add them read first 'b' read next 'b's and add ...
7
votes
3answers
574 views

Why is the Kleene star operator also called the Kleene 'closure' operator?

I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept. I don't understand why the ...
0
votes
0answers
36 views

$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \{x\#x^R \mid ...
0
votes
2answers
41 views

Intersection of regular and not regular

$L_1=\{a^n\mid n\ge1\}$ is regular and $L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular. We know that $L_1\cap L_2$ is regular but, here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?
4
votes
0answers
79 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
3
votes
1answer
23 views

Automata for languages derived from an automaton by number of state visits

My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer? I get how the languages are formed; however, since $M_L$ cannot remember how many ...
2
votes
1answer
72 views

NFA - string acceptance (decision problem) test

I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind. What is the complexity of ...
0
votes
1answer
39 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
1
vote
0answers
46 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
3
votes
4answers
768 views

What is the point of finite automata?

Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?
2
votes
0answers
31 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third [duplicate]

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ ...