Questions tagged [automata-theory]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

Filter by
Sorted by
Tagged with
1
vote
0answers
179 views

Edit-Distance of weighted automata

I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter). ...
0
votes
2answers
172 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
0
votes
1answer
225 views

is determining an unknown CFL from intersection of two CFLs decidable?

this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ...
0
votes
1answer
173 views

Does every regular language contains a strictly locally testable language?

Let $L$ be an infinite regular language, then does there exists a strictly locally testable infinite language $P$ such that $P \subseteq L$?
0
votes
1answer
454 views

Theta functions of automata relations

Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $._A$ (resp. $._B$) the action induced by $\Sigma^*$ over $Q(A)$, i.e....
0
votes
3answers
211 views

A fsm with temporal events

I have defined a finite state machine Q = {Σ, S, s0, δ, F} where Σ = {'[r]equest', '[o]ut', '[i]n', '[e]nd'} S = {'[R]eady', '[I]nitiating', '[W]aiting', 'Re[C]eived', 'Re[S]...
0
votes
1answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
0
votes
1answer
159 views

Where does a C-like language without heaps belong in the automata hierarchy?

Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without ...
0
votes
2answers
124 views

finite automata under morphism [closed]

Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$ Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted ...
0
votes
1answer
158 views

Implicit Non-deterministic Buchi determinization

I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states. But instead of using acceptance states, I am using final state (as in ...
0
votes
1answer
86 views

Difference between locally testable and it's boolean closure

A language $L$ is called i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that $$ w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq I....
0
votes
0answers
56 views

Information theory for Mathematical Physics [duplicate]

What are some good introductory texts on information theory for someone who is classically trained in mathematical physics? Unfortunately my abilities in computer sciences and formal logic are next ...
0
votes
0answers
58 views

Language recongized by a “quasi realtime register machine”?

Counter machines are very powerful. Even two counters suffice for making these Turing complete. But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. ...
0
votes
0answers
149 views

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
0
votes
0answers
77 views

Generalizing a set of positive and negative examples through DFAs [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint ...
0
votes
0answers
208 views

formal definition of “flowcharts”

I am looking for a formal definition of so-called "flowcharts" used as representation of programs or business processes. Is there some good one around ? Thx JCLL
-1
votes
1answer
75 views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

Is there inherently ambiguous language which can not be recognized by Deterministic LBA? For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
-1
votes
1answer
90 views

What is the formal definition of a stacked based finite state machine?

The formal definition of a finite state machine is as follows: A FSM is a quintuple: ($I$, $S$, $S$0, $T$, $F$) $I$ - finite, non-empty input set $S$ - finite, non-empty state set $S$0 - initial state ...
-1
votes
1answer
84 views

Issue in understanding conditional likelihood for a producton rule

The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
-1
votes
1answer
1k views

How to XOR automata? [closed]

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online. x XOR y XOR z = ((x|y)(~x|y)|z) (~((x|y)(~x|y))|z). This is way too ...
-1
votes
2answers
122 views

Looking for menu-driven coding editor based on a programming language state machine [closed]

I'd like to know whether an application development environment exists that uses a menu-driven coding editor that employs a programming language state machine. This would mean that commands, variable ...
-1
votes
1answer
44 views

Push Down Automata [closed]

Can we put more than one element in stack at a time. Actually I am asking that this transition function is valid for PDA: ∆(q,a,z)=(q',aaz) Where: q and q' are states a is input symbol z is starting ...
-1
votes
1answer
91 views

When designing a DFA, am I allowed to design two separate Machines and perform an Intersection on them? [closed]

I am trying to design a DFA s.t. The set of strings in x ∈ {0, 1}∗ such that the number of zeros is a multiple of 3 and the number of one's is even. My idea was to create two Machines M1 = (Q1, Σ, δ1,...
-1
votes
1answer
106 views

Constructing automata with the same traces, but where a CTL-formula is not equally satisfied [closed]

Hard to put this question in a short title. As part of a self-exercise, I'm trying to solve 6.15b of Principles of Model Checking by Baier and Katoen. You're supposed to prove that there does not ...
-1
votes
0answers
117 views

How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)? [closed]

How do you say "δ:Q×Σ→Q" in English? Describing what "×" and "→" mean would also help.
-2
votes
2answers
380 views

Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]

How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?
-2
votes
1answer
72 views

DPDA with parameterized states

I'm considering an extension of Sublime Text's syntax definition format. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to ...
-2
votes
1answer
602 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($...
-2
votes
1answer
210 views

Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis [closed]

Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis. For example, $(abaab)(bbbaa) \in L$, while $(...
-2
votes
0answers
26 views

Design a NFA and DFA which accepts: (1+01)*(0+00)(1+10)* [closed]

This is the DFA I came up with, but it does not match the answer. I can't find the mistake. Any help will be appreciated
-2
votes
2answers
206 views

An algorithm that determines if regular language accepts all string of its alphabet [closed]

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
-3
votes
1answer
708 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
-4
votes
3answers
518 views

Time-based mathematics or logic [closed]

The conventional systems of logic can only recognize or perform operations that transform or translate values in space. Ordinary logic treats time poorly through the necessity of translating all ...
-4
votes
1answer
312 views

Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
-4
votes
1answer
57 views

Prove that L* is a regular language [closed]

Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
-5
votes
1answer
2k views

Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...