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

learn more… | top users | synonyms

2
votes
1answer
54 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
69 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
1answer
217 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
68 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
22 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
40 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 ...
7
votes
2answers
6k 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.
0
votes
1answer
85 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
56 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
82 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
53 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
71 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
15 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 ...
0
votes
0answers
57 views

Converting a DFA to an NFA: Start State

When we try convert some NFA $N = (Q_N,\Sigma,\delta_N,q_0,F_N)$ to a DFA $D = (Q_D,\Sigma,\delta_D,\{q_0\}, F_D)$, why is it that $q_0$ becomes $\{q_0\}$? (Where $q_0$ is a single start state, ...
1
vote
2answers
25 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 ...
0
votes
0answers
82 views

Formal Languages: String Notation

In formal languages, we usually denote an alphabet $\Sigma$ as the set of symbols it contains, e.g. $\Sigma = \{0,1\}$ is the binary alphabet. It can be confusing because we denote $\Sigma^1$, the ...
2
votes
1answer
139 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
0answers
25 views

CF grammars and productions that are not CF

I'm learning about CF (context-free) grammars and I thought I understood what CF meant but I want to make sure I'm getting this concept. So I'm using some examples to make sure I'm understanding: $S ...
0
votes
1answer
32 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
48 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
41 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
249 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
30 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
140 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
83 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
150 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
35 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
24 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
25 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
27 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
71 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
50 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 ...
0
votes
1answer
54 views

Construct an automaton by using sliding window method

Given alphabet $\Gamma = \{0,1\}$, let $L = \{\omega : All\ words\ ending\ 010\}$ be a language. Find an automaton. I have to find an automaton using sliding window method.. First I need some ...
2
votes
3answers
127 views

Matrix representation of Automata

Is anyone know if there is any tutorial for the matrix representation of automata?? I am taking a theoritical computer science in this semester and the professor uses the matrix in his lecture. I ...
1
vote
3answers
64 views

Why is this the $L(M)$ of this DFA?

Why is this the $L(M)$ of this DFA? Can someone please explain it? I am new to this course. When I tried alone answering the question of "What is special about the words that get accepted by this ...
3
votes
1answer
552 views

Give a push down Automata for this language: the length of is odd and it's middle symbol is 0

Give a push down automaton for this language: {w| the length of w is odd and it's middle symbol is 0} Here is the CFG I wrote for this language: ...
0
votes
1answer
63 views

Automata and power series

I am taking a class on Automata and Formal Languages and I need to solve an exercise, but I have no idea where to start from. It sounds like this: Decide the coefficients of the words in ...
0
votes
1answer
208 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
1answer
36 views

Is this language regular ? [automata]

Is this a regular language : $$L = \{w : w \in \{a,b\}^*\text{ and }abw = wba\}$$ Does my automata only need to start with $a$ and $b$, then loop on $a,b$ and finish with $b\to a$, or do I don't ...
0
votes
2answers
154 views

Is it true that any infinite subset of a non-regular unary language is non-regular?

My question is very similar to this: Is there a subset of a non regular language that is regular My claim is that because the subset is infinite, Myhill Nerode says that the language is not regular. ...
0
votes
2answers
104 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
2answers
80 views

Finite state automata for two regular languages

I have to draw FSAs that accept the following languages over {0,1} and {a, b} (0 | 1)* a* | b* Now for 1, the language is just any word that consists of 1s and 0s but it also contains the empty ...
2
votes
0answers
26 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
1answer
271 views

Verification: DFA/NFA that accepts all strings over $\{0,1\}$ with exactly one block of $00$

I am trying to design a DFA or NFA that accepts all strings over $\Sigma = \{0,1\}$ in which the block $00$ appears only once. Here is what I've tried. Can you verify that this accepts all string ...
1
vote
1answer
33 views

Post-concatenation of the languages represented by the null set

I have a small question regarding concatenation of regular languages: Is it true that the concatenation $L\varnothing$, where $L$ is any regular language, result in $\varnothing$? Namely, does ...
2
votes
1answer
45 views

NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: ...
1
vote
0answers
81 views

Constructing an NFA accepted by a grammar

Contruct an NFA of the language accepted by the grammar below. $$G=(\{S,A,B\}, \{a,b,c\},S,P)$$ $P: S\rightarrow abaS\ \ | \ cA\\ \ \ \ \ \ \ A\rightarrow bA\ \ | \ cB \ \ | \ aa\\ \ \ \ \ \ ...
0
votes
1answer
106 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
48 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
27 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...