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

learn more… | top users | synonyms

-1
votes
1answer
23 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
1
vote
0answers
22 views

NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both. [on hold]

Im not sure if I am understanding this question correctly. Its a problem without a solution in my text. Starting with 1, and at least 01 or at least 010 or both these substrings..... So a regular ...
2
votes
1answer
641 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
1answer
588 views

Create DFA that accept language where number of 0's is even and after every 1 goes 0

Alphabet ${} = \{0,1\}$. Language $L = \{ w \in \{0,1\}^* \mid \text{ number of $0$'s in $w$ is even and after every $1$ goes $0$} \}$. I'm trying to create DFA that accepts language $L$. ...
0
votes
1answer
20 views

Is dead state only linked with the final state in any automata?

I am very much new to this subject and as far as I have tried the small research I found this most meaningful at this link Dead State - A rejecting state that is essentially a dead end. Once the ...
0
votes
1answer
53 views

Boolean formulas over omega automata

I've been reading on omega automata(automata on infinite words) and stumbled upon a definition involving logic which caught me off guard. For example, on Buchi automata the definition I originally ...
-1
votes
2answers
47 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
2
votes
2answers
49 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 ...
4
votes
3answers
3k views

Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
0
votes
0answers
23 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
27 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
0
votes
2answers
44 views

Can finite automata keep track of history or relevant history?

I am unable to understand that if I have a Finite automaton which say accepts all the strings that end with ab, now if input given is "aab" now it reads 'a', then it reads second 'a',this implies ...
2
votes
1answer
49 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 ...
6
votes
2answers
95 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$ ...
1
vote
0answers
56 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
2answers
34 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 ...
1
vote
2answers
56 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
28 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 ...
2
votes
2answers
33 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
1answer
21 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
37 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 ...
4
votes
3answers
170 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.
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?
2
votes
1answer
40 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
22 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
11 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 ...
17
votes
3answers
24k views

Difference between NFA and DFA

In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.
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) ...
1
vote
2answers
43 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 ...
0
votes
1answer
61 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 ...
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 ...
3
votes
1answer
876 views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following $$f(x,y) = x\times y$$ How to approach this problem in binary base? This is a assignment so I don't want anyone to solve it ...
1
vote
0answers
34 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
28 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 ...
3
votes
1answer
96 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
2
votes
1answer
26 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 ...
0
votes
1answer
36 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
78 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
26 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 = \{\}$ ...
1
vote
2answers
778 views

Find a CFG for L = { a^nb^m : n != m }

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. Find a context free grammar for $L = \{ a^n b^m : ...
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
55 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 ...
0
votes
1answer
22 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 ...
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 ...
1
vote
1answer
38 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
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
26 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 ≤ ...