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

learn more… | top users | synonyms

3
votes
2answers
169 views

Automata: 1=2, 2= 26, 3=1054, 4=5768, 5 =139314069504, 6 = ???

I am in my own Automaton (finite-state deterministic automata) research, so i have four sets of automata. 2 states automata, 3 states, 4 states and 5 states. Input alphabet $\{0,1\}$ so... the ...
0
votes
1answer
44 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
2answers
130 views

An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
115 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $? My attempt: $G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$ S\to AbBC $$ $$A \to ...
1
vote
1answer
157 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
0
votes
0answers
300 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
-1
votes
1answer
191 views

Decidability/Undecidability Question

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability. Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
2
votes
1answer
125 views

DFA worst case states

Suppose an NFA which accepts language of the form L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.} Then the corresponding DFA would have 2$^n$ states(worst case of subset construction). If we are to ...
1
vote
1answer
400 views

Proving Language accepted by DFA

I am stuck with a problem, as my proving skills aren't good(trying to improve). Prob: Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, ...
0
votes
0answers
78 views

Pumping Lemma length, $K$ for context-free language

Please help me understand, and if possible, tips, to determine a pumping length $K$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
1answer
132 views

Decidability of a Turing machine always halting in at most ten steps

I've exam comping up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove your ...
2
votes
1answer
301 views

Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
2
votes
1answer
64 views

Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
0
votes
1answer
299 views

Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.

I have exam coming up and I need help with this: Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3 Thank you :)
2
votes
2answers
98 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
1
vote
2answers
1k views

Concatenation of 2 finite Automata

I have some problems understanding the algorithm of concatenation of two NFAs. For example: How to concatenate A1 and A2? A1: ...
1
vote
1answer
45 views

Can every regular language have a linear bounded automaton

As the question states: I am trying to understand automata. Can every regular language have a linear bounded automaton?
2
votes
1answer
81 views

Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
1
vote
4answers
148 views

Non-Deterministic Turing Machine Algorithm

I'm having trouble with this question: Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language: $$ L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
0
votes
1answer
550 views

Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
2
votes
2answers
2k 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. ...
2
votes
2answers
124 views

Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.

I'm having my exam in few days and I would like help with this Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
4
votes
2answers
445 views

Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
0
votes
1answer
42 views

Automata: Proof

Here is the problem: Consider a NFA, M = (K, Σ, Δ, s, F) with (p, a, q) ∈ Δ. Prove that (pʹ, aw) ⊢∗ (qʹ, w) for any w ∈ Σ∗, q′ ∈ E(q) and p′ with p ∈ E(p′). Thanks in advance.
7
votes
1answer
272 views

What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?

In the Wiki page A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular ...
1
vote
2answers
346 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
3
votes
2answers
138 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
2
votes
2answers
315 views

Regular Languages Algorithm?

I need help proving the following question: Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length. So far, I know ...
3
votes
1answer
175 views

Context Free Language? Proving through grammar?

I need help solving this question: Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language? That is the number of $a$'s equal the number of $b$'s equal twice the ...
3
votes
2answers
94 views

If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 ...
0
votes
1answer
80 views

Questions about DFA with Sigma* exiting arrow and RE

Assume Sigma* contains all english alphabet chars. Then in my DFA, I have an exiting arrow of Sigma* and another exiting arrow of "a"(symbol from the alphabet) from one state. Will this be a valid ...
0
votes
1answer
262 views

An infinite context free language can be split into two infinite regular languages

Prove or disprove Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
-1
votes
2answers
80 views

Is λ={λ} true or not

I know that λ={λ} is true i want to know How can i prove that λ={λ} is true or not? Thanks in advance.
0
votes
3answers
541 views

Is indistinguishability an equivalence relation?

Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, ...
3
votes
1answer
332 views

Would the following NFA accept all strings?

The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or less. Does it follow that N accepts all strings? (If so, ...
1
vote
1answer
148 views

How would I go about proving for this NFA?

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following: N accepts the string x if the number of distinct ...
3
votes
2answers
415 views

Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
0
votes
1answer
66 views

How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
1
vote
2answers
174 views

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
1
vote
1answer
298 views

Finite state machine to report when the last 4 inputs were 1011

Suppose you want to construct an FSM containing one input and one output. Consider the example: The machine should assert the input (set to 1) when the last four bits taken in as input match the ...
2
votes
2answers
1k views

suffix regular language

Can someone give me an idea how to prove this: suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
1
vote
2answers
77 views

Proving this language is regular?

Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language? I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, ...
1
vote
3answers
93 views

regular language?

I need help proving whether this language is regular or not. $$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$ That is, the number of $a$'s is even and the ...
2
votes
1answer
547 views

How to construct a grammar $G$ such that $L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\} $?

Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$ My attempt: I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$, $G_1 = (\{ S\}, ...
1
vote
2answers
87 views

What are the states of this NFA?

I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states: $q_0$: the string ends with bb. ...
0
votes
1answer
53 views

Büchi Pushdown System Accepting Run

From the following definitions: Definition (Büchi Pushdown System) A Buchi pushdown system (BPDS) is a tuple BP = (Q,S,→,Qf) with (Q,S,→) a PDS (where S is the stack content) and Qf ⊆ Q a set of fi ...
1
vote
1answer
328 views

Nondeterministic finite automaton proof

I am having a really hard time working the problem below out. I am not sure I am even on the right direction with this logic . Swapping the accept and reject states alone is not sufficient to accept ...
0
votes
1answer
900 views

Reachability graph for Petri net.

I am trying to draw a reachability graph for this Petri net. Could you please help me to understand how this works?
0
votes
3answers
658 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
3
votes
0answers
1k 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 ...