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

learn more… | top users | synonyms

1
vote
1answer
37 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
80 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
138 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
385 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 ...
1
vote
2answers
1k 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
113 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
335 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
40 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
257 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
296 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 ...
2
votes
2answers
126 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
234 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
170 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
92 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
68 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
254 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
78 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
312 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
279 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
124 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
355 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
51 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
161 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
259 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
887 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
72 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
495 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
81 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
46 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
251 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
706 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
619 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 ...
0
votes
1answer
77 views

L is a context free language over {0, 1}, prove, disprove:

cont... L is a context free language over {0, 1}, prove, disprove: L1 is a CFL over {a, b}, where L1 is the language of all words from L, that 0 is converted to a and 1 is converted to bba. Thanks ...
1
vote
2answers
628 views

How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
1
vote
0answers
141 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
0
votes
1answer
131 views

Number of states required for deterministic finite automata

Lemma in text: Let $c$ be a constant and $L = \{1^c\}$ (the singleton language containing the string of $c$ many 1's). Then no DFA with < $c$ states can accept $L$. The given proof assumes ...
1
vote
1answer
387 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
0
votes
1answer
90 views

Prove min(L) = all words in L that they don't have any prefix of themselves in L

We define the minimal words language of $L, \min(L)$, to be the language of all words in $L$ that don't have any prefix in $L$. Assume $L$ is regular language. I need to prove by building an ...
1
vote
1answer
311 views

Show that every finite automaton is a one-state pushdown automaton

I'm reading a book that states: Every finite automaton is a one-state push-down automaton How can I go about proving it?
1
vote
2answers
421 views

Showing that a language is regular - Pushdown Automaton

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
0
votes
3answers
104 views

showing that a regular language is regular after taking a letter off or after adding letters

I'll be happy to recieve help with this one: Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular: $\{xy\mid xay\in L\}$ ...
0
votes
1answer
629 views

Formal proof of the concatenation of two regular languages automaton

During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation). The ...
2
votes
1answer
60 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
1
vote
2answers
94 views

Solve right linear set equations

Trying to solve this set of equations. I'm feeling like I'm making it so complicated. Of course + is union. Am I on the right track? A = 0B + 1D B = 0C + 1A C = 0A + 1B + λ D = OD + 1C + λ A ...
0
votes
2answers
319 views

Proof Two Grammars Generate the Same Language

I have two right linear grammars and I need to prove they both generate the same language. What is the right way to do it? L1: $S \rightarrow 0A$ $S \rightarrow 1B$ $A \rightarrow 0A$ $A ...
0
votes
1answer
78 views

Is this NFA correct?

For the language L = $\{\Sigma^*. 0 .\Sigma^5 . 1. \Sigma^*\}$ The NFA must have 8 states. Also, what would be the upper bound on the number of states of a DFA recognizing L.
1
vote
1answer
54 views

Is this NFA correct for the language {w | w ends with an a and no a occurs between any occurrences of b}?

Language: {w | w ends with an a and no a occurs between any occurrences of b} The NFA must have exactly 3 states.
0
votes
3answers
76 views

Is this DFA correct for the language $\{w \mid w \in \{ab\}^*\}$?

Language: $\{w \mid w \in \{ab\}^*\}$