Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
0
votes
1answer
183 views
Is it always possible to convert a non-deterministic PDA to a deterministic one?
Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
1
vote
1answer
277 views
Turing Machine Vs Linear Bounded Automata
Example of language accepted by Turing Machine but not by Linear Bounded Automata ?
Is there any EXPSPACE language?
7
votes
2answers
342 views
A magic trick with synchronizing words
See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html
Spoiler Alert
Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
186 views
Density of black cells in rule 110
Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.
Simulation of first 120000 ...
0
votes
1answer
61 views
How many neighbours should a cell have in a cellular automata?
So, I'm currently working with cellular automata but I started to wandered, what's the perfect amount of neighbours each cell should have if I'm working in a bi-dimensional space?
Up to now I was ...
0
votes
3answers
132 views
Word problem in a free group
Can the word problem in a free group be solved by a finite state automaton?
I know it can be solved by a pushdown automaton.
4
votes
1answer
119 views
Minimal DFA satisfying a finite view of a language.
Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq ...
1
vote
1answer
47 views
what is the effect of adding another stack to a PDA
does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?
3
votes
2answers
275 views
Help in constructing a DFA equivalent to this NFA
First post here, woot. I've been a member of Stack Overflow for a while, so hopefully you guys are just as friendly!
I'm having issues converting simple NFAs to DFAs... I just don't get it. ...
0
votes
2answers
302 views
String matching automata preprocessing
I have an alphabet A = {a,b,c} and a pattern P = "abcaab".
The task is to build a finite automaton of the transition function (delta) for {0,6} (the length of the pattern) and each element of the ...
1
vote
2answers
57 views
Closure property of Alternating language
Problem Given a language $L$ is context-free, must $\operatorname{alt}(L)$ is also context free? where $$\operatorname{alt}(L) = a_1a_2a_3 \ldots, \quad L = a_1b_1a_2b_2a_3b_3 \ldots$$
I couldn't ...
1
vote
1answer
126 views
Finite Automata, basic question with semigroups
If we use the notation where when we say:
$$M = M(G)$$
We mean to say that $M$ is a automata with states and alphabet elements of $G$.
From here, I am posed this question (Abstract Algebra by ...
2
votes
1answer
511 views
Nondeterministic PDA to Deterministic PDA
Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
1
vote
1answer
154 views
CFG pumping lemma
I can't figure out how to prove this is a non CFG.
$\{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}$, Where the number of a's in x = number of a's in y and number of b's in x = to the ...
0
votes
2answers
196 views
How can I prove that this language is regular?
Given a language $L$, define the language $K$ as the language $L$ where every second character is replaced with a $\#$. (Note: $\#$ is not part of the alphabet of $L$.) For example, if $L = \{ab, ...
0
votes
1answer
469 views
Extended transition function of a DFA - a proof
I would like to write a proof of the following statement
$$
\delta^+(q,PQ) = \delta^+(\delta^+(q,P),Q)
$$
$\delta^+$ - Extended transition function
I have to do it by induction. However, I'm not ...
1
vote
2answers
450 views
NFA to DFA conversion, half the power set
Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
0
votes
3answers
137 views
Having trouble with “languages”
Okay, so I come across a question:
What language is represented by this regular expression:
$$(((a*b)b) \cup b)$$
An example given prior to this is:
L(anguage) = $\{w | w \in \{0,1\}\}$
L(anguage) ...
1
vote
1answer
493 views
Unable to construct Context-free Grammar from Pushdown Automaton
I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata.
I can construct a CFG, but it ...
1
vote
1answer
88 views
What is this operation between sets {a, b}{c, d} do?
Not sure what this operation does, which is why i'm on here. It's not the cartesian product and no idea what it's called. I need to know to prove:
For any language L, (Null set)L = L(null set) = ...
2
votes
3answers
195 views
What is the language of this DFA?
How would you write the language for this DFA as L(M) = {...}?
I think in English I would say L(M) is defined as {a,b}* ending in b, ba or aa.
0
votes
2answers
107 views
How to represent a formal proof
I know how I want to do the proof, but I don't know how to represent it. It's an automata proof, so all I need to do is show that it is regular. How could I represent a DFA as a copy? So I have the ...
2
votes
1answer
349 views
Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$
Problem
Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$
For the language $wcw^R$, it's much easier because the stack is always empty after ...
2
votes
2answers
1k views
Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$
Problem
Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$
My initial idea was,
If we read an $a$ push a $x$ onto stack
If we read a $b$, there are two ...
3
votes
1answer
344 views
Question regarding stack operation notation in PDA
I'm currently reading two books:
An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz.
Introduction to the Theory of Computation, 2nd Edition by Michael Sipser.
What ...
1
vote
1answer
119 views
Question regarding the initial stack symbol in Push Down Automaton
Let $L = \{a^nb^n : n \geq 0\} \cup \{a\}$, where $\Gamma = x, \$, \Sigma = {a, b}$, we have the NPDA of $L$ in three states:
In the above state diagram, I can break the transtion $\lambda, \lambda ...
2
votes
2answers
151 views
Is it possible to prove that $L$ is a regular language?
Let $L = \{a^{f(m)} | m \geq 1 \}$ where $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ is monotonically increasing and complies that for all $n \in \mathbb{Z}^+$ there is $m \in \mathbb{Z}^+$ such that ...
3
votes
3answers
458 views
Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?
Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular?
I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
1
vote
4answers
5k views
Convert from DFA to NFA
For this language $\{ w | w \text{ contains at least three } 1's \}$, its DFA diagram is defined as follows:
While trying to convert it to NFA, but I realized that its NFA would be identical to ...
2
votes
1answer
263 views
Understanding and using the transfer-matrix-method
Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in ...
3
votes
3answers
1k views
How to prove two regular expressions are identical in mathematical way?
I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is ...
0
votes
2answers
401 views
Find the DFA for the language $L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$
Problem
Find the DFA for the language $$L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$$
This is a problem from the book "An Introduction to Formal Languages amd Automata 4th edition", ...
3
votes
2answers
414 views
How to compute the transition function in non-determinism finite accepter NFA?
I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51):
...
0
votes
1answer
252 views
Proving regular expressions to be equivalent
I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof).
The process is to show that R1 is a subset of R2, and ...
0
votes
1answer
146 views
Complementary language of a context free grammar
First post on Mathematics ;)
I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary ...
2
votes
1answer
166 views
Generating all words in a language from CFG
I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines?
This can be done with an abvious brute-force search by ...
3
votes
0answers
66 views
Enhancing the monoid structure over a finite alphabet to prove Arden's rule
Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the ...
0
votes
0answers
281 views
Regular Expression Simplification
Hi my question about Theory of Computation is:
Let $M$ be defined as follows
$$M = (K; E; s; D; F )$$
for
$$
\begin{align*}
K &= \{q_0, q_1, q_2, q_3\}, \\
E &= \{a, b, c\}, \\
s &= ...
3
votes
1answer
1k views
How to show that $ALL_{DFA}$ is in P
How can I show that $ALL_{DFA}$ is in P ?
$ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
1
vote
2answers
224 views
Is this DFA correct
I'm supposed to construct a DFA which accepts
{ w | w is a word except 'aa' and 'aaa' }
Is this the correct solution? The thick line state is supposed to be the end state.
EDIT
Sry, somehow ...
0
votes
2answers
1k views
Understanding $\epsilon$ transitions in a finite state automaton
I am trying to understand how $\epsilon$ transitions work.
From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those ...
2
votes
1answer
659 views
Nondeterministic Finite Automata to Deterministic Finite Automata?
I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
1
vote
5answers
3k views
Program for working with DFA/NFA/PDA?
I'm looking for a program or utility to help construct DFA/NFA/PDA etc. and the like.
The main reason I'm interested in this, is because I want to be able to move the various states around without ...
