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

learn more… | top users | synonyms

1
vote
1answer
840 views

Language that is recursively enumerable, but not recursive

I have a problem with this task: Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
1
vote
1answer
47 views

Show Two f.s.a. machines accept different input

I'm trying to solve it for two hours already. I know it somehow related to the pumping lemma Let $M_1 = \langle Q_1,S,f_1,s_1,F_1\rangle$ and $M_2 = \langle Q_2,S,f_2,s_2,F_2\rangle$ be two machines, ...
1
vote
1answer
841 views

Show two finite state machines are equivalent

Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines. I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ ...
1
vote
2answers
387 views

Can _any_ NFA be converted to a DFA?

I was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and ...
0
votes
1answer
350 views

Creating a minimal dfa from a regular expression

Having a bit of difficult with the following question: Create a minimal dfa for the language $L(r)$ where $r = a^*\bigl((ab+b)^*\bigr)$?
1
vote
2answers
358 views

For the regular expression, (a* + b*) . (a.b)* , does the following automaton recognise the language it describes?

I constructed the automaton below using the assumption that the language described by the regular expression above only accepted the following strings: Empty, aabab, babab, aaaabab, bbbabab etc ...
0
votes
2answers
71 views

What is the difference between the automatas for the regular expressions (a + b)* and (a* + b*)?

I know that the automaton for the regular expression (a + b)* will just have one state, where the initial state = the accepting state and there is one edge going into that state labelled a,b. Sorry, ...
0
votes
1answer
118 views

Proving what are the equivalence classes of the relation $R_{L}$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$ The TA wrote that "this is not what you should prove" (or "this ...
0
votes
0answers
94 views

A question about the language of a non-deterministic FSA defined by a non-deterministic FSA with epsilon moves

I have tried to solve the following problem and my claims were marked as wrong, I would appreciate it if someone could point out my mistake Let $A=(Q,\Sigma,q_{o},\delta,F)$ be a finite state ...
1
vote
0answers
111 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
1answer
98 views

Is the language $\{i|f(i)=1\}$ recursive, function $f$ is described further inside. [duplicate]

Possible Duplicate: Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s $$L = \{i\mid f(i)=1\}$$ $f(i)$ equals $1$ if ...
1
vote
1answer
56 views

Proving $\{ll^{R}l|l\in\{a,b\}^{*}\}$ is not context free using the pumping lemma

How can I prove, using the pumping lemma for context free languages, that $\{ll^{R}l|l\in\{a,b\}^{*}\}$is not a context free language ? I tried to put $n$ as the pumping lemma constant and chose ...
0
votes
1answer
52 views

Legal actions on a PDA and terminology

I am unsure about the following so I would like to verify if my statements are true: We can remove at most a single character ($Z\in\Gamma$) from the PDA (top ?) of the stack with one step of the ...
0
votes
1answer
149 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
148 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
90 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
97 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
102 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 ...
0
votes
0answers
35 views

Proof two FSM are k-equivalent [duplicate]

Possible Duplicate: Confusion related to state equivalence of finite state machines Show that p is k-equivalent to q, if and only if that any x belongs to S*, |x|=k, g(p,x)=g(q,x) Any ...
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
606 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
173 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
176 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
218 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
103 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
208 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
126 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
321 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 ...
0
votes
1answer
72 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
120 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
238 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
161 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
83 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
361 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
103 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
208 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
141 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
92 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
424 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
214 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
87 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
776 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
168 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
151 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 ...