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

learn more… | top users | synonyms

0
votes
3answers
311 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
273 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
348 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
158 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
256 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
863 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
490 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
246 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
686 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
611 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
624 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
129 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
377 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
302 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
413 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
101 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
621 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
92 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
314 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\}^*\}$
1
vote
1answer
823 views

Language that is recursively enumerable, but not recursive

I have a problem with this task: Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
1
vote
1answer
47 views

Show Two f.s.a. machines accept different input

I'm trying to solve it for two hours already. I know it somehow related to the pumping lemma Let $M_1 = \langle Q_1,S,f_1,s_1,F_1\rangle$ and $M_2 = \langle Q_2,S,f_2,s_2,F_2\rangle$ be two machines, ...
1
vote
1answer
810 views

Show two finite state machines are equivalent

Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines. I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ ...
1
vote
2answers
367 views

Can _any_ NFA be converted to a DFA?

I was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and ...
0
votes
1answer
336 views

Creating a minimal dfa from a regular expression

Having a bit of difficult with the following question: Create a minimal dfa for the language $L(r)$ where $r = a^*\bigl((ab+b)^*\bigr)$?
1
vote
2answers
334 views

For the regular expression, (a* + b*) . (a.b)* , does the following automaton recognise the language it describes?

I constructed the automaton below using the assumption that the language described by the regular expression above only accepted the following strings: Empty, aabab, babab, aaaabab, bbbabab etc ...
0
votes
2answers
71 views

What is the difference between the automatas for the regular expressions (a + b)* and (a* + b*)?

I know that the automaton for the regular expression (a + b)* will just have one state, where the initial state = the accepting state and there is one edge going into that state labelled a,b. Sorry, ...
0
votes
1answer
118 views

Proving what are the equivalence classes of the relation $R_{L}$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$ The TA wrote that "this is not what you should prove" (or "this ...
0
votes
0answers
93 views

A question about the language of a non-deterministic FSA defined by a non-deterministic FSA with epsilon moves

I have tried to solve the following problem and my claims were marked as wrong, I would appreciate it if someone could point out my mistake Let $A=(Q,\Sigma,q_{o},\delta,F)$ be a finite state ...
1
vote
0answers
108 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
1answer
98 views

Is the language $\{i|f(i)=1\}$ recursive, function $f$ is described further inside. [duplicate]

Possible Duplicate: Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s $$L = \{i\mid f(i)=1\}$$ $f(i)$ equals $1$ if ...
1
vote
1answer
56 views

Proving $\{ll^{R}l|l\in\{a,b\}^{*}\}$ is not context free using the pumping lemma

How can I prove, using the pumping lemma for context free languages, that $\{ll^{R}l|l\in\{a,b\}^{*}\}$is not a context free language ? I tried to put $n$ as the pumping lemma constant and chose ...
0
votes
1answer
52 views

Legal actions on a PDA and terminology

I am unsure about the following so I would like to verify if my statements are true: We can remove at most a single character ($Z\in\Gamma$) from the PDA (top ?) of the stack with one step of the ...
0
votes
1answer
149 views

Proving that for every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$

The book I am reading have proof for the statement Every context-free language there exist a pushdown automata $M$ s.t. $L=L_{e}(M)$ For the case $\epsilon\not\in L$. The proof uses greibach ...
0
votes
1answer
145 views

Proof related to a finite state machine

I have this confusion related to a finite state machine M such that if the number of states n>=2, then there exits i $ \overset{i}\equiv{}= {\overset{i+1}\equiv{}}$ I mean the $i^{th}$ equivalence ...
2
votes
1answer
88 views

Definition of a deterministic Pushdown automaton

According to my book the definition of a deterministic Pushdown automaton allows for $\delta(q,\epsilon,Z)$ to be non-empty if $$\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$$ Can someone ...
1
vote
2answers
97 views

Pushdown automata - definition and definition of $\vdash$

I am reading about pushdown automata and I don't understand the definition of $\vdash$. My book writes that $$(q,aw,Z\alpha)\vdash(p,w,\beta\alpha)$$ if $$(p,\beta)\in\delta(q,a,Z)$$ Can someone ...