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

learn more… | top users | synonyms

0
votes
1answer
68 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
57 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 ...
1
vote
1answer
76 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
49 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
50 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
61 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
33 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
34 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
17 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
23 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
38 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
18 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
85 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
99 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
34 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
60 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
37 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
41 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
32 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
60 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
42 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
61 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
66 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
65 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
40 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
32 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
31 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 ...
0
votes
1answer
14 views

finding a regular length

i am trying to find a regular language that: her minimum pumping length = number states of minimum Nondeterministic automata that receive the language = number of equivalence classes. (not 1) any ...
1
vote
2answers
38 views

Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$. Let $L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many ...
0
votes
1answer
36 views

Prove about $NFA$ and pumping lemma

The question: Let it be $L$ a regular language. few definitions: $p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma. $n(L)$- minimal NFA that accepts $L$. $m(L)$- $Rank(L)$, the ...
0
votes
1answer
26 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular ...
0
votes
1answer
40 views

which of the following languages are regular?

If w,x,y ∈ (a+b)^+ 1)L=wxwy 2)L=xwyw 3)L=wxyw According to me all of them should be non-regular since we can't actually check what will be the starting symbol of first occurrence of w since it ...
0
votes
1answer
25 views

Prove that relates to pumping lemma that I am not sure about

So, I will define like in my last post (for a regular language $L$): We will define $p(L)$ to be the minimal natural number so that a language $L$ fulfill the pumping lemma. We will also define ...
0
votes
0answers
27 views

How to prove that a simple NFA is minimal, without any algorithm?

First, I will present the question I was doing: We will define $p(L)$ to be the minimal natural number so that a language L fulfill the pumping lemma. We will also define $n(L)$ to be the minimal NFA ...
0
votes
0answers
24 views

what is the relation between CFG , LL(K) ,LR(K) and regular grammars?

I am clear with only the concept that LL(k) grammars are the one which are a subset of context free grammar and are not left-recursive ,and LR grammars are one which are parsed by bottom up parsers ...
0
votes
1answer
30 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 ...
1
vote
1answer
20 views

Proving this language is non context-free

How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple ...
0
votes
0answers
27 views

Is the resulting language regular?

If $L$ is a regular language then is $L'=\{w \mid wx \in L \text{ for some string }x\}$ regular? First step is understand $L'$. So it is a subset of $L$ that contains strings with a certain prefix?
0
votes
1answer
127 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 ...
0
votes
1answer
24 views

Identify the class of language?

Given a set $$S=\{x∣ \text{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). Identify class of language? Somewhere it ...
0
votes
1answer
40 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: ...
0
votes
1answer
26 views

Designing a DFA to accept a string

I have created the following FA Im i correct?
1
vote
0answers
58 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
39 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr ...
1
vote
1answer
21 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...