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

learn more… | top users | synonyms

6
votes
0answers
112 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
3
votes
0answers
95 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
3
votes
0answers
250 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, X)...
3
votes
0answers
48 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
3
votes
0answers
2k views

My Moore and Mealy machines look the same. Why?

For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with ...
2
votes
0answers
99 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. Shouldn'...
2
votes
0answers
77 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
284 views

nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use (bi)...
2
votes
0answers
45 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
2
votes
0answers
42 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
2
votes
0answers
77 views

halting problem

Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ...
2
votes
0answers
161 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
0answers
77 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
2
votes
0answers
33 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton $X$...
2
votes
0answers
66 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
53 views

Quality of Reduction of finite automata

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a ...
1
vote
0answers
43 views

What are some properties that the regular languages are not closed under?

In a standard Theory of Computation class, one learns a variety of closure properties of regular languages, including but not limited to: homomorphism, inverse homomorphism, union, complement, ...
1
vote
0answers
3 views

Turing machine with k-dimensional tape or k-regular tree

The statement I read is " In a k-dimensional tape, cells corresponds to elements of free commutative group of k generators. s. There are 2k shifts, which correspond to addition of a generator ...
1
vote
0answers
18 views

If $G$ is $LL(k)$, then $L(G)$ is a deterministic context free language.

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). For every grammar, If the correct production can be deduced from the partially ...
1
vote
0answers
37 views

Turing Machine make use of another Turing Machine

I am expected to formally construct a deterministic TM to compute a function. I already have a TM for $f(x)$. How can I make use it formally while constructing $g(x)$? $g(x)$ is like in the followig ...
1
vote
0answers
18 views

How to make the NDPA of this question?

Say $w^R $ is the reverse of $w$. E.g.: $\epsilon^R = \epsilon$ and $(abbab)^R = babba$ Now say $L = \{ww^R | w \in L (a^*b^*)\}$ Draw the NDPA $M$ with $L(M) = M$ I understand NDPA's, however I ...
1
vote
0answers
34 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
1
vote
0answers
22 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
1
vote
0answers
17 views

Verify correctness of this PDA

I'm trying to construct a PDA for the language $\{a,b\}$ where there are the same number of $a$'s as $b$'s. This is what I have, but I'm skeptical on the correctness. Can anyone verify?
1
vote
0answers
24 views

Converting CFG to PDA for $S\to aSd|aBd\\B\to bBc|\varepsilon$

I need to build a pushdowm automata for the context-free-grammar $$S\to aSd|aBd\\B\to bBc|\varepsilon$$ My attempt: I'm not sure if my attempt is correct or not.
1
vote
0answers
61 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be invalid....
1
vote
0answers
19 views

Deterministic FSM accepting a binary string whose number of zero is either multiple of 2, 3, or both

I can build a FSM that accept binary string with multiple of 2 number of 0, and I can also build a FSM that accept binary string with multiple of 3 number of 0, but I cannot figure out how I can ...
1
vote
0answers
44 views

why is automaton with a queue is more powerful than an automaton with a stack?

what is the logic behind this statement that with the use of queue the automaton becomes more powerful , is it that in a queue , we may do operations from both the ends as compared to a stack so it is ...
1
vote
0answers
47 views

Evaluating $b^*a^*\cap a^*b^*$ to a minimal regular expression

Evaluate to a minimal expression: $b^*a^*\cap a^*b^*$ To me, the only elements to both sets are the empty string, strings containing only $a$, and strings containing only $b$, so isn't the answer ...
1
vote
0answers
111 views

The set of all strings with twice as many 0's as 1's

I have to create a PDA that accepts strings with twice as many 0's as 1's. So far I have decided to create one which accepts via empty state: (q0, 0, Z0) - (q1, 0) (q0, 1, Z0) - (q1, 11) (q1, 1, 1)...
1
vote
0answers
27 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
1
vote
0answers
29 views

Are languages that contain the empty string Turing-Decidable?

Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable? I am very confused at this problem because from my understanding the ...
1
vote
0answers
27 views

Intersection automaton of two automata

I need to build the intersection automaton of these two automata My attempt: My attempt is correct?
1
vote
0answers
40 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
1
vote
0answers
83 views

Does a mathematical construct exists which explains all theories?

If I am not wrong quantum mechanics is about measurements of different physical properties and probabilities of getting different outcomes. We have a mathematical construct to explain it, that is how ...
1
vote
0answers
55 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
1
vote
0answers
79 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is non-...
1
vote
0answers
65 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', \...
1
vote
0answers
30 views

question about determinstic pushdown automata

i need to show that there is no DPDA accepts the language $L=\{a^n*b^n \mid n>0\}\cup\{a^n*b^{2n} \mid n>0\}.$ i used the prefix property but i'm stuck showing that if $w,w' \in L$, $w$ is ...
1
vote
0answers
60 views

What is the highest state in the context of finite state automata?

I am doing an assignment for my Theory of Computation course. We are writing a function and I am having a hard time understanding what "highest" state means in the following context: ...
1
vote
0answers
339 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
1
vote
0answers
74 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
1
vote
0answers
48 views

how to create transition system/automata for modulo 4

I don't know how to think when to build a transition system/automata to calculate modulo 4 a of binary numbers. I know that the last two binary digits gives the rest but I need to go through hole ...
1
vote
0answers
78 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
1
vote
0answers
122 views

Create a finite-state machine

I need to create a finite-state machine which accepts strings whose characters are in {a,b,c} and produce output strings of T's and F's. The machine outputs a T once the characters ab is encountered ...
1
vote
0answers
161 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph theory,...
1
vote
0answers
27 views

Can the NFA constructs be minimized?

When converting a regular expression to a NFA you need to use certain constructs. My question is can these constructs be minimized? We have one with 4 states, I want to use the one with 2 states ...
1
vote
0answers
65 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
1
vote
0answers
93 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
1
vote
0answers
49 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...