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

learn more… | top users | synonyms

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
18 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 ...
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 ...
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) = ...
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
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
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 ...
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$, ...
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
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 ...
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
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!
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
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
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) ...
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
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 ...
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
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 ...
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
27 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
47 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 ...
0
votes
1answer
21 views

Acceptance by final state PDA and acceptance by empty stack .

Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state ...
0
votes
1answer
22 views

Trying to figure what language this PDA (pushdown automata) accepts

I have the following PDA and I can't figure our what words it accepts, would like to get some help with figuring this out. Of course it only accepts if that stack is empty in the accepting state.
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 ...