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

learn more… | top users | synonyms

0
votes
1answer
151 views

Proving that for every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$

The book I am reading have proof for the statement Every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$ For the case $\epsilon\not\in L$. The proof uses greibach ...
0
votes
1answer
164 views

Proof related to a finite state machine

I have this confusion related to a finite state machine M such that if the number of states n>=2, then there exits i $ \overset{i}\equiv{}= {\overset{i+1}\equiv{}}$ I mean the $i^{th}$ equivalence ...
2
votes
1answer
94 views

Definition of a deterministic Pushdown automaton

According to my book the definition of a deterministic Pushdown automaton allows for $\delta(q,\epsilon,Z)$ to be non-empty if $$\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$$ Can someone ...
1
vote
2answers
98 views

Pushdown automata - definition and definition of $\vdash$

I am reading about pushdown automata and I don't understand the definition of $\vdash$. My book writes that $$(q,aw,Z\alpha)\vdash(p,w,\beta\alpha)$$ if $$(p,\beta)\in\delta(q,a,Z)$$ Can someone ...
0
votes
1answer
107 views

Finding if two machines can be equivalent

I have this problem: Consider the following machines M1 and M2. M1 has initial state A and the initial state of M2 is unspecified. Can the machines be made equivalent by the correct choice of ...
2
votes
2answers
3k views

Design Push Down Automata to accept palindrome by empty stack

I'm trying to make a PDA that accepts the language w001(rev w) | w = {0,1}* by empty stack, where rev w means the reverse of w. (Stack symbol = #) I've come up with this so far, but I don't know how ...
2
votes
2answers
716 views

Existence of NFA of a reverse of a language

Hi, I'm really stuck on how to prove the following: Given that $L$ is a language and $L'$ is a set such that $L' = \{w \mid w' \in L\}$ where $w$ is the reverse of $w'$, e.g., if $w = a a b$ then $w' ...
1
vote
1answer
185 views

finite state machine is strongly connected

Let M be an n-state reduced strongly connected finite state machine. prove there exists an input string $w$, where $|w|\le n(n-1)/2$, s.t. M assumes each of its states at least once in response to ...
1
vote
0answers
186 views

Confusion related to state equivalence of finite state machines

I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
0
votes
1answer
47 views

Given two NFAs, is there a way to figure out if there exists a language that works for both of them?

Given two non-deterministic finite automaton, is there a way to determine if there exists a single language that satisfies them both?
4
votes
3answers
239 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
2
votes
2answers
52 views

Derivation of a property of a language

I am confused how this relation is derived for a language on alphabet V A,B The relation is $$ (A\cup B)^*=(A^*B^*)^* $$ I am confused how this is derived. Any pointers?
0
votes
2answers
37 views

Confusion related to a property of languages on some alphabet V

I came across this relation betwen tww sets of languages formed from the alphabet V. A,B The relation is $$ A^*\cup B^* =((A\cup B)^*)^* $$ I am confused how this is derived. Any pointer?
6
votes
1answer
106 views

Existence of NFA for this language

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
1
vote
1answer
213 views

Examples of epsilon transitions

I understand the meaning of epsilon transitions, but could someone give example where epsilon transition becomes handy?
3
votes
3answers
128 views

Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular

Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$. I wish to prove that $L$ is regular using only closure properties (such as ...
2
votes
1answer
69 views

Is $f$ is computable by a finite automaton, the dual of $f$ is thus computable also?

et $A$ be a finite alphabet. Let $A^*$ denote the language of all words in $A$, and $\epsilon$ the empty word. Let $\rho : A^* \to A^*$ denote the "reverting" map, that transforms $a_1a_2\ldots a_n$ ...
1
vote
1answer
328 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
1
vote
1answer
75 views

Regular expression arithmetics

What are the rules of regular expression arithmetics ? For example: Let $\Sigma=\{0,1\}$ $1. 1+01=(\epsilon+0)1$. $2. (\epsilon+00)^*=(00)^*$
0
votes
1answer
123 views

A question about the regular languages being closed under Boolean operation (how to generalize)

I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$ are regular languages, I also know that $L$ is regular $\implies L^{c}$ is regular . It is easy to ...
3
votes
1answer
243 views

Proving Turing Completeness by Simulating Rule 110

Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial ...
3
votes
2answers
66 views

Does $L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ s.t when $M$ runs on $w$, $M$ visits some state at least $k$ times$\} \in R$?

I'd like your help with understanding , how come the following language is decidable (in $R$): $L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ such that when $M$ runs on $w$, $M$ ...
1
vote
1answer
169 views

Random cellular automaton with three colors.

Does exist a Cellular Automata Rule that is RANDOM (like rule 30) and has 3 colors? I mean, as Wolfram says in his book, rule 30 shows a random behavior with some limits. But this happens using 2 ...
0
votes
1answer
84 views

How to prove that the language of a DFA is some $L$

Consider the following DFA: It is quite clear that the language of this FDA is all the words that don't have the word $aa$ as a subword. My question is: How can I formally prove that this is the ...
0
votes
2answers
380 views

DFA and NFA equivalent language

I'm asked to build a DFA A and NFA B such that L(D) = L(N) with some specific conditions. I'm not asking for solutions or answers; I just wanted to make sure I have the right method to attack this ...
0
votes
1answer
108 views

Help with set notation?

I want to describe the set of all words in the following format: a0w1 where a represents EITHER 0 or 1, and w represents {0,1}* So 00011 is valid as is 1010011, etc. etc. I'm really new to set ...
7
votes
1answer
211 views

Does there exist a universal pushdown automaton?

Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such ...
2
votes
1answer
142 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
1answer
97 views

Conditions for: $xy=zw$ and $yx=wz$

Let $x,y,z,w$ be finite strings. Find the necessary and sufficient conditions for the following two equations to hold simultaneously: $$xy=zw$$ and $$yx=wz$$ Automata Theory is new to me and i am ...
0
votes
1answer
75 views

something that looks sort of symmetrical but also not

Given the set $S_0$ of finite binary strings whose digit sum is congruent to 0 mod 2 and the set $S_1$ of finite binary strings whose digit sum is congruent to 1 mod 2, what are the implications of ...
9
votes
2answers
442 views

Why is it undecidable whether two finite-state transducers are equivalent?

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
0
votes
3answers
220 views

Different version of pumping lemma and how to prove it

I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs. Consider the following version of pumping lemma. For any ...
1
vote
1answer
91 views

How to formally describe this Uppaal automata?

I have the following simple automata: What I'm looking for is a formal description of this based on the definition here $A=(\Sigma,\Gamma,S,s_0,\delta,\omega, F)$ How to declare all the ...
2
votes
2answers
900 views

The language that contains no proper prefixes of all words of a regular language is regular

Let $L$ be a regular language. I need to prove that the language $$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$ that contains all words of L that do not have a ...
1
vote
2answers
175 views

Pushdown Automaton

Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language $(a^3+a^5)$* using as few states as possible? How can this be done using a ...
1
vote
1answer
152 views

Which automata recognise the algebraic numbers?

I am reading historical stuff on the algebraic and transcendental numbers. Descartes, in his Geometry, excluded all curves not expressible as algebraic equations. Later, Leibniz called such curves ...
3
votes
4answers
6k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
4
votes
1answer
63 views

Gliders, static structures in various (dynamic) systems

Structures, i.e. symmetries over time, appear in various systems: gliders in cellular automata, like Game of Life or Rule 110, unmatched string's parts in rewrite systems – unchanged in multiple ...
7
votes
3answers
5k views

Why does this FSM accept binary numbers divisible by three?

This final state machine accepts binary numbers that are divisible by three. In theory the states should equal to the value $n$ mod $3$, but how does this work for binary numbers? What I don't get ...
2
votes
1answer
217 views

Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct? (4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions: (i) 0 My Answer 4ci (ii) ...
5
votes
1answer
78 views

Is there any relationship between the bounding box and the period of an oscillator in the Conway's Game of Life?

Is there any relationship between the bounding box and the period of an oscillator in the Conway's Game of Life? In particular I am interested in this case: what is the maximum period for an ...
2
votes
1answer
134 views

Two elementary question on automaton and language

1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language? PS:The reason ...
3
votes
2answers
110 views

How to ensure the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$

Show that the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$ in the sense that, for every semigroup $S$ recognizing $X$, there exists a morphism from $S$ onto the syntactic ...
2
votes
2answers
336 views

Checking if the language is a regular one

Let A = $\{x \in \{a,b\}^{*} \mid |x|_{a} = |x|_{b} \}$. Is possible to find a regular expression $\alpha$ such that $L(\alpha)$ = A ? $L(\alpha)$ is the regular language defined by $\alpha$. It ...
0
votes
0answers
278 views

Deterministic Finite Automata: State Diagram Notation

Refer to the paper Radu Grosu, "Finite Automata as Time Invariant Linear Systems - Observability, Reachability and More". I have a problem understanding the state transition diagram of DMA $M_1$ in ...
4
votes
1answer
560 views

Drawing a PDA for a language

I am initiating myself into TOC and using sort of random resources from the web. I was looking at this problem from a Berkeley problem set: Construct a PDA to accept $$ L = {a^ib^j|i \neq j , 2i ...
2
votes
3answers
122 views

Regular Language

Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this ...
4
votes
1answer
124 views

Is $(p,\epsilon,p)$ a path of an automaton?

$A$ is an alphabet. An automaton over $A$ can be defined as a set $A_0 = (Q, E, I, T),$ where $Q$ is the set of states, $E \subseteq Q \times A \times Q$ is the set of edges or transition, $I, T ...
6
votes
1answer
307 views

Automata theory on infinite words: any video lectures?

I am fun of automata theory. Can you suggest good video lectures on the subject? (there is a good one here, but it is accessible from RWTH University only)
0
votes
1answer
60 views

Modelchecking on Automata, $\phi$ not SAT and $\phi \models$ False

Given a formula $\phi$ Is $\phi \models FALSE$ equivalent to $\phi$ not SAT? Or does $\phi \models FALSE$ means that $\phi$ is never $TRUE$ and $\phi$ not SAT means, that there existst at least one ...