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

learn more… | top users | synonyms

1
vote
1answer
71 views

One counter automata

A one-counter automaton $M = (Q, S, \Gamma, t, s, A)$ is a pushdown automaton where the stack alphabet $\Gamma$ contains just two symbols $\#$ and $g$. The symbol $\#$ is initially written on the ...
2
votes
0answers
64 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
0
votes
2answers
66 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
1
vote
1answer
156 views

unrestricted grammar and Turing machines

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ ...
3
votes
1answer
107 views

reverse automata mininum states

There is a formal proof for the following sentence? For every $k$ there is a DFA (deterministic finite automaton) $M$ with $k+2$ states such that every automaton that accepts the language $L(M)^R$ ...
2
votes
1answer
252 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
0
votes
1answer
107 views

DFA with $k$ states, words of length $k$

Is this statement true? If we have a DFA with $k$ states, and if $L(M) = L$ is infinite, then there is a word of length at least $k$ and at most $2k-1$. Isn't this a trivial answer? Take the ...
0
votes
0answers
32 views

Is this a context-free language?

Let $L = L_1^* \circ L_2^*$ where $L_1 = \{1^n 0^m 1^n : n,m \in \Bbb N\}$ and $L_2 = \{0^m 1^{2m} : m \in N\}$. Is the language $L$ a context free language? I think I can write automata for $L_1$ ...
1
vote
0answers
52 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
0
votes
1answer
47 views

Question about second condition of pumping lemma

I don't think that I fully understand how to use the pumping lemma to prove that a given language is not regular. I'm reading Sipser and according to him the definition of the pumping lemma is: "If A ...
0
votes
0answers
36 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
2
votes
1answer
283 views

Converting CFG to CNF

I have the following problem of converting CFG to CNF: $$ \begin{aligned} S \Rightarrow\,& bA \mid aB\\ A \Rightarrow\,& bAA \mid as \mid a\\ B \Rightarrow\,& BB\mid bs\mid b ...
0
votes
1answer
450 views

Converting NFA to DFA

Im trying to convert a NFA to DFA. This is the NFA and this is the DFA to which i converted Is this right? Also when converting if i write a state as [q0,q1] is this same as [q1,q0] edit: ...
1
vote
1answer
54 views

If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular?

I've encountered a question during my studies: If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular? I thought to disprove it by using $A\subseteq 2\mathbb{N}, L=\{w\in\{0\}^*:|w|\notin A\}$ ...
1
vote
1answer
182 views

Proving a set is language generated by given grammar

I have grammar $G$ with productions $S\rightarrow aS|aSbS|\epsilon$, and task is to prove that $L(G)=\{w|$every prefix of $w$ has at least $a$'s as $b$'s$\}$ (I'm not sure if translation is correct, I ...
0
votes
1answer
88 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
271 views

Grammar Construction from Given Language!

Just a fast question! I have this language L(G) = { z^n * x^2n with n>=1 } What is the grammar ? I think it should rather be: ...
1
vote
1answer
622 views

Languages and Grammar (Finding a language)

I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have $N= \{S , C ,D\}$, $T=\{c, d\}$ and $P = \{S \to Dc, D \to Dd, D \to ...
1
vote
1answer
62 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
0
votes
2answers
46 views

Building an automaton that defines a language

I have $2$ languages, $L_1$ and $L_2$, both are part of $L$-dfa. I have the following language: $$L_0= \{a_1\cdot b_1\cdot a_2\cdot b_2\cdot\ldots a_n\cdot b_n \mid a_i,b_i\in\Sigma, ...
0
votes
1answer
25 views

How is Finite Automation Linked to Lexical Analyser

I understand that Finite Automaton is a Mathematical model of a system with discrete number of input and outputs. Also the system has finite number of states.My question is how is this linked with ...
2
votes
1answer
75 views

Formal proving of languages accepted by a finite automata.

Suppose $L_1 \cup L_2,L_1 \subseteq E^* $ are languages accepted by finite automata and $L_1\cap L_2 =\emptyset $. We need to prove that $L_2 $ is also accepted by a finite automaton. So I've started ...
1
vote
2answers
71 views

New automaton that runs two others step by step?

If I have two automatons for two languages ($M_1, M_2, L_1,L_2$ respectively), what would be the procedure to mix them by defining a new automaton such that the new automaton would accept the words ...
0
votes
2answers
404 views

Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?
0
votes
1answer
84 views

Designing PDAs to Accept Languages

I want to design PDAs to accept the following two languages: $L_1 = \{a^ib^jc^k \mid i=j \text{ or } j=k\}$ $L_2 = $ The set of all strings with twice as many $0$s as $1$s. I am especially ...
2
votes
1answer
27 views

Properties of “fail-safe” languages

I'm wondering if anyone has any experience with the concept of a "fail-safe" language. And, if so, where could I find more information on the subject. To explain what a "fail-safe" language is: Let ...
1
vote
1answer
52 views

Equivalence of two PDAs

I want to show that if $P$ is a PDA, then there exists a PDA $P_2$ with only two stack symbols, such that $L(P) = L(P_2)$. As I want only two stack symbols for $P_2$, it seems intuitive to encode in ...
16
votes
3answers
22k 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
175 views

Is $\epsilon$ in every alphabet?

Given a $\Sigma$ an alphabet, is $\epsilon$ in it logically? For example, if I have a function $ f : \Sigma \to \Sigma $, can I define it for example $ f(\sigma) = \epsilon$? even if my alphabet is ...
1
vote
1answer
64 views

If $L \cdot \{\epsilon, a, b\}$ is regular, is $L$?

Given that $L \cdot \{\epsilon, a, b\}$ is regular, is $L$ regular too? (Our alphabet is $\Sigma = \{a,b,c,d\}$ What I thought was yes, and here is why: If it is regular, then we know there ...
1
vote
2answers
95 views

If $L_2L_1$ is accepted by a DFA, is $L_1$ too?

Given that $L_2, L_2L_1$ are accepted by a DFA, is $L_1$ accepted by a DFA too? What is the general approach to such question? What if instead of $\cdot$ we are given that $L_2 \cup L_1$ is ...
1
vote
1answer
72 views

About described DFA

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
0
votes
1answer
75 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
27 views

Binary Comparison using automata

The question is: Construct a DFA, which accepts the following language, $\{\omega | \omega = a_1b_1a_2b_2...a_nb_n\}$ for some n, where $b_i, b_i\in \{0, 1\}$ and $a_1a_2...a_n > b_1b_2...b_n$ I ...
1
vote
2answers
35 views

Construct a deterministic finite automation

The question asks to: construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n. I have no idea where to start to constructing the ...
2
votes
1answer
279 views

DFA Transition Function Inductive Proof

Show for any state $q$, string $x$, and input symbol $a$, $\hat\delta(q, ax) = \hat\delta(\delta(q, a), x)$, where $\hat\delta$ is the transitive closure of $\delta$, which is the transition function ...
0
votes
1answer
38 views

Grammar derivation

Given these grammar productions: $$\begin{align*} &S\to A1B\\ &A\to 0A\mid\lambda\\ &B\to 0B\mid 1B\mid\lambda \end{align*}$$ And given string $w = 01101$ If I wanted to make a) ...
0
votes
1answer
59 views

Showing a grammar to be ambiguous

I'm learning about grammar ambiguity and trying to show the following grammar is ambiguous: $S \rightarrow ScS | SdS | A$ $A \rightarrow a | b$ I used 2 different left-derivations to get the same ...
2
votes
1answer
46 views

CF grammar on this language

I'm trying to write a context-free grammar for this language: $L = \{a^n b a^m (bb)^n : m \ge 1, n \ge 0\}$ I was getting lost with maintaining $n$ number of $a$'s and $(bb)$'s and I'm not sure how ...
2
votes
2answers
648 views

Lambda productions in grammar

I tried removing the $\lambda$ productions from this grammar: $S \rightarrow a A b \mid B B a$ $A \rightarrow b b \mid \lambda$ $B \rightarrow A A \mid b A a $ It seems like you just take away the ...
0
votes
1answer
38 views

S-grammar for this regular expression

Given this regular expression: $r = a a^* b + b^* c b$ I think this is the simple grammar, but I was getting a little lost with the productions: $S \rightarrow S_1 | S_2$ $S_1 \rightarrow a A b$ ...
1
vote
1answer
214 views

Greibach normal form conversion

I'm trying to convert this into GNF: $S \rightarrow ASaa | bab$ $A \rightarrow Ba | bAB$ $B \rightarrow abba$ So I'm getting this, but I'm not sure understanding and applying correctly the concept ...
0
votes
1answer
181 views

Grammar into Chomsky Normal Form

Convert the following grammar into Chomsky Normal Form (CNF): S → aS | aAA | bB A → aA | λ B → bB | aaB I think this looks ok, but not sure. Maybe someone can point out where I go wrong: ...
1
vote
1answer
338 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
0
votes
2answers
54 views

Subset of A Regular Language

I need to show that a subset of a regular language is regular or not. I think it may not be regular but I could not find a counter example. Do you have any simple example to prove that? Thanks in ...
0
votes
2answers
33 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
1answer
34 views

Give an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct.

Given an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct. We define the matrix as follows. Let $L \subset \Gamma^*$ where $\Gamma$ is alphabet. Then the ...
0
votes
1answer
42 views

Construc a DFA for given language

The given language is this. $$L = \{a^nb : n \geq 0\}$$ Let $M = \left<\{q_0,q_1,q_2\},q_0,\Gamma=\{a,b\},\delta,\{q_2\}\right>$ be a DFA, where $q_0$ is the initial state, $q_2$ is the accept ...
0
votes
2answers
81 views

Can someone explain this automaton?

I have a question about constructing an automaton for given language: $$L = \{000, 010, 100, 110\}$$ Solution for this was given below. Can anyone explain why this automaton accepts the language? This ...
1
vote
2answers
54 views

If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$?

Given the words $v,w \in \sum^*$, is this correct? If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$ If $vw^2 = wv^2$ then $v=w$ For one, I tried $v=\epsilon, w=\epsilon$ and it worked, and ...