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

learn more… | top users | synonyms

-3
votes
2answers
25 views

induction odd length of 1's automato

Consider the following automaton, $A$. diagram I tried using the method of induction to prove that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. and to Show that there ...
1
vote
1answer
21 views

A proof question involving a regular set and a context free language

Claim: Let $L \subseteq \Sigma^*\{\#\}\Sigma^*$ be a context-free language, where $\# \notin \Sigma$. Suppose that for each $x \in \Sigma^*$, $\{y|x\#y \in L\}$ is finite. Then $\{y|\text{ for some } ...
0
votes
0answers
23 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
0
votes
1answer
19 views

power + operator for binary

What is the specific definition for power $+$ operator in automata theory? For example, when $x$ is a binary what does it mean that $x = 0^+$. Does it mean that x is a string with at least one $0$?
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
14 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 ...
-2
votes
1answer
34 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
24 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
24 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
48 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 ...
2
votes
1answer
42 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 ...
3
votes
1answer
58 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
36 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
12 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) = ...
0
votes
0answers
35 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
36 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 ...
0
votes
1answer
27 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$, ...
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 ...
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 ...
1
vote
1answer
29 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 ...
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 ...
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 ...
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 ...
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.
0
votes
1answer
48 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!
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
29 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
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 ...
0
votes
1answer
47 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) ...
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 ...
1
vote
1answer
41 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 ...
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 ...
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} ...
1
vote
1answer
22 views

Construction of DFA using an odd bit of language

I am working through a lecture and it constructs a DFA using the language: $$\{w\mid w\textsf{ is any string not in }(ab^+)^\ast\}$$ What does the $(ab^+)$ mean?
1
vote
1answer
39 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
0
votes
3answers
31 views

Language of Regular Expression

I'm trying to teach myself Regular expressions for Automata, I'm struggling to work out what the output of $L((1+01)^*)$ would be Would it be the star closure of $\{1,01\}$ or star closure of ...
1
vote
1answer
54 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 ...
0
votes
1answer
25 views

what is the complement of the language L={ww : w ∈{a,b}* }

The given language is not CFL ,it is CSL and CFL is not closed under complement operation ,Now I am not getting how to find it's complement ,please tell the approach .
0
votes
0answers
28 views

Converting Automata To Regular Expression Using State Removal Method

From the following automaton this solution is given: $$(a\mid b)^*aa(ba)^*a(a\mid b)^*$$ But when I try to convert this automaton into a regular expression I always end up with the wrong ...
0
votes
2answers
45 views

what is the complement of empty language?

If R- Regular language , C-Context Free language and L -Recursive language then what is the result of the expression ((R-C)-L)',Now first starting with R-C , It will give result as ∅, since every ...
2
votes
1answer
48 views

Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...