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

learn more… | top users | synonyms

2
votes
1answer
18 views

Finite automata as dynamical systems

In abstract (deterministic finite) automata theory the set of states of an automaton is an arbitrary set Q, and the transistion function is a specific set δ ⊆ Q × Σ × Q (with alphabet Σ, i.e. another ...
1
vote
0answers
51 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 ...
6
votes
2answers
90 views

Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
2
votes
1answer
40 views

DFA/NDFA problems confirmation

Im studying for a test on my own and have been working through some previous test questions. Can anyone help me confirm that the answers I've gotten for the problems below are correct or not. If there ...
1
vote
2answers
33 views

How to design a finite state automaton that recognises the languages like $1^n 0^n$

The question goes like this: Design a finite state automaton that accepts binary strings with at least two $0$s and at most two $1$s. I can easily design an NFA which accepts at least two $0$s OR at ...
2
votes
2answers
24 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
1
vote
2answers
49 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
1
vote
1answer
19 views

is language accepted by finte state automaton

Hi I need to prove these languages are accepted or not by the following finite state automata. for 1 does this mean that we need an even number of a's or that a is literally 2,4,6,8....etc also ...
2
votes
1answer
36 views

Why is this language not regular?

I am studying Automata using the Coursera course created by Jeff Ullman. On slide 36 of this presentation: http://spark-public.s3.amazonaws.com/automata/slides/3_fa2.pdf it says that the language is ...
1
vote
1answer
23 views

How to simulate a 3-stack automaton with a 2-stack automaton?

Since a 2-stack automaton is Turing-equivalent, it is possible to simulate a 3-stack automaton with just a 2-stack automaton. But how so? How it is normally done?
4
votes
3answers
153 views

Number of states in a finite automaton

How many states are required by a deterministic finite automaton to store $m$ words each of length $n$? I came across $2^{mn}$ as the solution but there was no explanation.
2
votes
1answer
38 views

Is the Champernowne constant an automatic number?

The Champernowne constant in base $b \geq 2$ is obtained by concatenating the $b$-ary expansion of every integer. For example, in base $10$ this is $$ 0.123456789101112131415\dotsc $$ Question: Is the ...
1
vote
1answer
21 views

Why Petri Net tokens are not added?

Reading this article it says: A firing of an enabled transition removes one token from each input place and adds one token to each output place. Now if I have the following net, with all ...
0
votes
0answers
10 views

inverse proof of closed under union

I am being posed the following question: given are languages $L_1, L_2, L_3 $ and $ L_4$. $L_1$ is a decidable language and $L_2$ and $L_4$ are both recognizable languages. Considering $L_1 = L_2 ...
1
vote
1answer
44 views

How n (1+b) is not prime?

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
0
votes
2answers
28 views

Why is the below language regular?

If I have a language $$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$ I am not getting how come we are able to write regular expression for this of the form $$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ...
2
votes
1answer
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
36 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
1
vote
1answer
26 views

Best approach to determine the equivalence classes of a formal language

I created a minimum automaton for a formal language using the Myhill-Nerode theorem. The language for which I created the automaton is defined by $L=\{w \in \{a,b\}^*:w=av \text{ for a word } v ...
1
vote
0answers
32 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 ...
0
votes
2answers
25 views

How to draw a DFA for complement of a regular language using a regular expression?

How can I draw an FA for the complement of the language $L(r)$? $L(r) = a^* (aba^*)^* b^* a^*$ I can draw an FA for $L(r)$ and convert to DFA and then take the complement, however it seems very long ...
1
vote
2answers
41 views

Proving that $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not a regular language

I'm having trouble using the pumping lemma to prove this language $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not regular. Assume $L$ is regular. Thus there is a DFA $M$ for it. Choose $m$ as the ...
2
votes
1answer
20 views

Concatenation of Finite Languages and Regular Languages

I know that the following statements regarding Concatenation are false. However, I'm having difficulty explaining why they are false with simple counter-examples. I'm able to find simple ...
1
vote
1answer
70 views

Why are Recursively enumerable languages closed under intersection?

when Recursively enumerable sets are not closed under complement ,then how come they are closed under intersection because the definition of intersection comes as L1 intersection L2= complement(L1' ...
-1
votes
2answers
25 views

Is the intersection of a finite language and an infinite language always a regular language?

Is the intersection of a finite language $L_1$ and an infinite language $L_2$ always a regular language? I've tried a few examples and the result always seems regular. $\{\} \cap a^nb^n = \{\}$ ...
0
votes
1answer
35 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
1
vote
1answer
26 views

Minimum Size of DFA

I'm confused about the following DFA problem: Let L denote the set of all strings in $\{a, b\}^∗$ that contain abb or aab as a substring. Show that any DFA that decides L must have at least five ...
0
votes
1answer
19 views

Proving from Myhill-Nerode that the minimum DFA is the smallest automaton recognizing $L$

From this paper, In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for ...
0
votes
1answer
52 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
1
vote
1answer
33 views

Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
0
votes
1answer
20 views

Find the language recognized by the given deterministic finite state automaton

I got 01* U 1(01)01 as my answer. I'm not sure if its right.
0
votes
0answers
13 views

4th case in Ogden's Lemma

I'm trying to understand Ogden's Lemma and I know there are four cases, but in the next example I can only find 3: A = {$0^n1^m0^k$ | k = max{n,m}} is not context free: Assuming: z = $0^k1^k0^k ∈ A$ ...
0
votes
1answer
24 views

How to find the right quotient of a language given two languages?

If $L_1= \{a^n b^m \mid n \geqslant 1, m \geqslant 1 \} \cup \{ba\}$ and $L_2= \{b^m \mid m \geqslant 0 \}$. I am not getting how the DFA for $L_1/L_2$ is constructed in the second figure ...
2
votes
1answer
43 views

Designing a Turing Machine - low level transitions

I couldn't figure out how to proceed with this question. Preparing for the finals, can someone explain how to do this step by step? Design a TM, write low level transitions for $\{a^i b^j :i ≤ j ≤ ...
1
vote
1answer
29 views

Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor ...
0
votes
2answers
37 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
2
votes
1answer
18 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
0
votes
1answer
29 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
0
votes
2answers
16 views

Languages and their Regular Expressions - Automata

I am working on some Automata practice problems. I am working a 2 part question. Here it is: Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$ ...
1
vote
1answer
29 views

Pumping Lemma proof and the union/intersection of regular and non-regular languages

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct. Parts b-d, I am not sure how to do it. I created a dfa ...
0
votes
1answer
21 views

Using the Pumping Lemma To Prove A Language Is Not Regular

I am taking a Automata class and we just went over the Pumping Lemma. Initially, it did not make sense. I am still not fully comfortable but I have started trying to use it to prove that a language is ...
2
votes
1answer
20 views

Prove that regular languages are closed under operation

Operation $random$ is defined on two words with equal length in the following way: $\forall w_1,w_2 \in \Sigma^* s.t. |w_1|=|w_2|=n, w_1=a_1a_2...a_n, w_2=b_1b_2...b_n:$ $Random(w_1,w_2) = ...
0
votes
1answer
28 views

Explain the semantics of concurrent languages with real analysis examples

In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. I need to explain the concurrency ...
0
votes
0answers
101 views

Determinitic finite automaton (DFA) that accepts natural numbers divisible by 6

I'm new to Formal Systems and Automata and I'm working on some exercises to get familiar with the concepts. I want to create a DFA that accepts natural numbers divisible by 6. I know that a number ...
1
vote
1answer
45 views

NFA (nondeterministic finite automaton) made out of the Bible?

Let B be the language over alphabet {a, ... z} consisting of those words occuring in the Bible. Thus, B = {in,the,beginning,god,created,...}. Describe an NFA whose language is B. Describe what ...
1
vote
1answer
45 views

Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$ could anyone help me?
0
votes
0answers
36 views

Is the sequence $(v_p(n))$ of $p$-adic valuations of positive integers the fixed point of a morphism, for every prime $p$?

Fix a prime number $p$ and consider the sequence $\mathbf{v}_p = (v_p(n))_{n \geq 1}$, where $v_p$ is the usual $p$-adic valuation, i.e. $v_p(n) = a$ iff $p^a \parallel n$. While browsing the OEIS I ...
1
vote
1answer
26 views

what do we mean by saying that a particular computing machine is more powerful than another computing machine?

I am having confusion in understanding the concept of the word "powerful" in automata theory. Even the confusion arises that if I have a DFA with single final state ,so then is it more or less ...
1
vote
1answer
32 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
2
votes
3answers
298 views

What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...