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

learn more… | top users | synonyms

0
votes
1answer
919 views

Create DFA that accept language where number of 0's is even and after every 1 goes 0

Alphabet ${} = \{0,1\}$. Language $L = \{ w \in \{0,1\}^* \mid \text{ number of $0$'s in $w$ is even and after every $1$ goes $0$} \}$. I'm trying to create DFA that accepts language $L$. ...
0
votes
2answers
18 views

Reverse of binary number

Let us say that x is a set of binary numbers $$x = \{0, 1, 1001\}$$ Am I correct that $x^R$ is equal $$x^R = \{0,1,1001\}$$ or is it: $$x^R = \{1,0,0110\}$$ What I mean by that is: do we create a ...
0
votes
0answers
12 views

FIRST of a grammar with righthand recursions

$L$ is defined by the grammar $$ S \rightarrow SAB \mid \epsilon \\ A\rightarrow Ba \mid \epsilon \\ B \rightarrow Ab \mid \epsilon $$ What is a $FIRST$ for elements of this grammar? I have two ...
-1
votes
1answer
28 views

proof that $L=\{a^{n}b^{n^{2}} | n\ge0\}$ is not context free language [on hold]

I need help to prove that $\mathcal L=\{a^{n}b^{n^{2}} | n\ge0\}$ is not context free language using the pumping lemma. thanks.
1
vote
1answer
19 views

Parser for reversed language

Language $L$ is specyfied by grammar : $(\{S,A,B\},\{c,d\},S,\{S \rightarrow SA, A \rightarrow Bc | \epsilon, B \rightarrow d\})$. My task is to construct LR(1) parsing table for language $L^R$ ...
1
vote
1answer
23 views

Finite Automata for regular expression

I am trying to construct finite automata for this regular expression: Every block consisting of 5 characters need to contain at least two zeros. The regular expression would look sth like this: ...
3
votes
1answer
45 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
0
votes
1answer
26 views

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free I am trying to prove it without to build a pushdown automaton First I tried to look which words are in $\mathcal L$, ...
2
votes
1answer
41 views

Is the complement of a given language context-free?

I have a problem with finding out if the complement of language L is context free. $L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s ...
0
votes
0answers
16 views

what is the minimum no of DFA states required to recognise below language?

$L=\{a^nk , k>0 \text{ and } n \text{ is an integer constant} \}$ In this question which constant should be changed , n or k while considering the DFA since then it can be either $n+1$ or $k+1$ ?
2
votes
1answer
43 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
0
votes
1answer
34 views

why is the below language a regular set? [closed]

Given a set S={x∣ there is an x-block of 5's in the decimal expansion of π} (Note: x-block is a maximal block of x successive 5's) In the question it is mentioned that there is x-block of ...
0
votes
1answer
11 views

Consider the given regular grammar what are the Myhill-Nerode equivalence classes for the language generated by the grammar?

S → bS | aA | ϵ A → aS | bA A) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #a(w) is odd} B) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #b(w) is odd} C){w ∊ (a + b)* | #a(w) = ...
2
votes
3answers
660 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 ...
0
votes
0answers
33 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that ...
-1
votes
2answers
34 views

Automata Theory - Designing a Non-deterministic Finite automata [closed]

I have been combing through youtube looking for a simple explanation on how to "crack" the "NFA" myth. Please help. Since drawing the schematic can be cumbersome, if you can show me how I can derive ...
2
votes
1answer
27 views

Let $Σ=\{a,b,c\}$. Which of the following statements is true?

$1)$ For any $A\subseteq\Sigma^*$, if $A$ is regular, then so is $\{x∣ xx\in A\}$. $2)$ For any $A\subseteq\Sigma^*$, if $A$ is context-free, then so is $\{x∣xx\in A\}$ According to me the ...
-1
votes
0answers
17 views

what is the no. of states of the FSM required to simulate the behavior of a computer with a memory capable for storing 'm' words? [closed]

All the m words are of n bits each , so how to many states are required in FSM ? According to me , since there are m words and each are of n bits so total length of input available to us is mn , and ...
1
vote
0answers
49 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be ...
0
votes
1answer
22 views

how to build a PDA for the language of the intesection of PDA and DFA

lets say we got PDA $M=<Q, \Sigma,\Gamma,\delta,q_0,+,F>$ ('+' marks the end of the stack) with $L_1 = L_f(M)$. and we got $A=<P,\Sigma,\delta_1.p_0.F_1>$ with $L_2 = L(A)$. how can I ...
0
votes
0answers
23 views

How many states needed for this FSM, and how do I define them?

I want to define states for FSM that gives an output $1$ if and only if $X$ is dividable by $5$ with a residue of 3. where $X$ is the binary number that the machine got until now (Not Including ...
1
vote
1answer
27 views

Converting an NFA to a DFA

I am trying to convert this NFA to DFA: So I built the power automata, and this is what I got: This should be the answer: I don't understand where am I wrong since ...
24
votes
4answers
36k 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
27 views

Using Pumping Lemma to prove that $L=\{a^mb^{3m}:m\in\mathbb{N}\}$ is not recognizable over $A=\{a,b\}$

[Pumping Lemma]: Let $\mathcal{A}=(Q,A,\cdot,i,T)$ be a (complete and deterministic) automaton and let $L=L(\mathcal{A})$ be the language recognized by $\mathcal{A}$. If $L$ is infinite and ...
2
votes
1answer
645 views
0
votes
1answer
14 views

when do we say a grammar to be unambiguous with respect to parse tree and derivation tree?

In normal terminology we say that both the parse and derivation trees are same in meaning so if a grammar derives one string with left derivation as well as right derivation then it is ambiguous , if ...
0
votes
1answer
66 views

What is the nature of given language?

$$L=\{a^n b^n :n\geq0, n\neq100 \}$$ I just wanted to know that through pda. How will we make sure that $n\neq100$ or say I put a restriction that $n\geq100$. How to design a PDA using these ...
0
votes
1answer
96 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
1
vote
1answer
52 views

Question about deterministic finite automaton and accepting states

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the set of the languages that can be accepted by "$1-$DFA" is a subset of the ...
0
votes
1answer
47 views

Is $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ a context free language?

I need some help in finding and proving (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ is a context free language. thanks!
2
votes
1answer
68 views

Question about deterministic finite automaton (DFA) [closed]

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the language $\mathcal L=\{0,00,0000\}$ cannot be accepted by any $2-$DFA.
1
vote
1answer
38 views

Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
1
vote
1answer
28 views

Synchronizing sequence

From Sipser's book: Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $h$ be a state of $M$ called its "home". A synchronizing sequence for $M$ and $h$ is a string $s\in \Sigma^*$ where $\delta ...
1
vote
1answer
30 views

Language with middle third removed

Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...
0
votes
2answers
32 views

which of these languages are regular sets?

$$ L_1 = \{a^p b^q\ |\ p+q \ge 10^6\} \\ L_2 = \{a^m b^n\ |\ m-n \ge 10^6\} $$ According to me both of these languages require comparison between number of $a$'s and $b$'s so both of them should ...
0
votes
1answer
33 views

Pumping lemma for two words that “completely different”

Let $"x"$ and $"y"$ be a words, we will say that two words are "completely different" if for all $1\leq i\leq |x|$ the $i$ letter in $x$ diffrent from the $i$ letter in $y$. Prove that the ...
0
votes
0answers
13 views

context-free-grammar for pushdown automata

I need to build context-free-grammar to this pushdown automata My attempt: $S=A_{03}$ because $q_{\color{blue}0}$ is the initial state and $q_{\color{blue}3}$ is the final state. There are $4$ ...
0
votes
0answers
16 views

Is the given language decidable or not?

L={|L(M) ={1} } Converting this in terms of program terminology I gee that given any input program we have to see whether it accepts "1" and nothing else . So for input 1 , if it accepts it then we ...
1
vote
0answers
17 views

Converting CFG to PDA for $S\to aSd|aBd\\B\to bBc|\varepsilon$

I need to build a pushdowm automata for the context-free-grammar $$S\to aSd|aBd\\B\to bBc|\varepsilon$$ My attempt: I'm not sure if my attempt is correct or not.
0
votes
1answer
25 views

DFA, best practice

Consider the following language {A,B,C} and the following regex (A|B)+C. I'm a little in doubt about which of my two examples is more correct. Or are they both equally correct? e.g., Is it allowed ...
0
votes
1answer
15 views

Determining whether a given language is regular, and finding a regular expression

I know there are a lot of questions similar to this one, Proving a language is regular is just one example. However, I have not managed to find an answer that really answers my question. I'm currently ...
0
votes
1answer
44 views

Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
2
votes
2answers
876 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
4answers
54 views

Determining if a binary string represents a prime integer

Let $\Sigma = \{0,1\}$ and $w$ be the string $0011101$ over $\Sigma$. If we work out what $w$ is, $w$ is the binary representation of $57$, which is not prime. It is remarked in Introduction to ...
1
vote
1answer
38 views

Prove that two arithmetic grammars generate the same language

In my university's automata theory book it is claimed that the following two arithmetic grammars generate the same arithmetic language but no proof is shown. $G_1=(\{E\}, \{a,+,*,(,)\}, \{E\to ...
1
vote
1answer
26 views

Prove that a given CFG grammer $G$ is equivalent to language $L$

I need help to prove that the given CFG grammar $G$ is equivalent to language $L$: as $S\to 0S1 \mid SS \mid \varepsilon$ and $L=\{w\in\{0,1\}^* \mid \#_0(w)=\#_1(w)\text{ and for any prefix } u ...
0
votes
0answers
23 views

How to find a push-down automata that describes $f_{\sigma}(L)$? (given that $L$ is context free language)

Let it be $L$ a context free language. Definition: $f_{\sigma}(L)$={$w:σw∈$$L$}. Need to find a push-down automata $M'$ so that $f_{\sigma}(L)$=$L(M')$. Ok, so here is my idea for ...
1
vote
1answer
53 views

If $A$ is regular, is the language $\{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$ regular?

Here is the question: Let $A$ be any regular set over some alphabet $\Sigma$. Is the language $$ L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\} $$ necessarily regular? I am unable to ...
3
votes
0answers
18 views

Finding a language the accepts a given push-down automaton [duplicate]

Ok, so given the following automaton: I need to find the language that accepts it (no need for formal prove, a short intuitive explanation is good enough). I think the answer here is {$a^{11+6k}, ...
0
votes
0answers
35 views

Language resulting in the same NFA as the DFA

I have tried to construct the NFA and DFA from the same language term, and they keep coming out the same, I was wondering if this is correct for: {w | w has an even length and an odd number of a's} ...