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

learn more… | top users | synonyms

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
58 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
39 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
57 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
59 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
59 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
37 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
29 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
34 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
24 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
18 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
23 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
118 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
38 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
57 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
38 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
18 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\}$ ...
0
votes
0answers
16 views

If M1 and M2 are 2 TM’s such that L(M1) = L(M2) , then which of the following conditions are true?

(a) On every input on which M1, doesn’t halt, M2 doesn’t halt. (b) On every i/p on which M1 halts, M2 halts too. (c) On every i/p which M1 accepts, M2 halts. How to approach this question ?
0
votes
0answers
10 views

transitively closed and NFA and DFA states

These are true or false questions given on a quiz. How can I approach these two statements: ( the "e" represents the $\lambda$) to find the correct answer. a. To make the $\lambda$ moves ...
0
votes
1answer
102 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
1
vote
1answer
27 views

Checking if Post Correspondence Problem has a Solution

I have the following problem I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?
0
votes
0answers
17 views

Conversion of CFG to Chomsky Normal Form

I have the following question I have answer for the first one as S->C1S C1->C2A C2->a S->C2A ...
0
votes
1answer
31 views

Build a DFA that accepts strings over $\{0,1,2\}$ that are divided by $3$ and doesn't include the substring $012$.

I am attempting to Build a DFA that accepts over $\{0,1,2\}$ that are divided by $3$ and doesn't include the substring $012$. What I tried doing is taking the original 3 states of a DFA that accepts ...
2
votes
1answer
34 views

Writing a regular expertion for the language $L=\{0^n1^m \mid n\equiv m\pmod 2\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
0
votes
1answer
12 views

Language of all the binary words that not contains continuum of more then $3$ zeros

I need to write a regular expertion for the language of all the binary words that not contains continuum of more then $3$ zeros, for example $0011110100\in L,\,\,\,\,\,\,\,\,\,11000001100\notin L $ ...
1
vote
1answer
75 views

Design a DFA to check whether the Given Number is Even

I have the following question I have designed the following A Binary String is even if it is ending with 0 and odd if its ending with 1.I have applied this.Im i right ? UPDATE:
0
votes
1answer
26 views

Language of all the binary words that contain $010$ at least twise

I need to write a regular expertion for the language of all the binary words that contain $010$ at leasr twise, note that $101010$ should be accept too because $1\color{blue} {010}10$ and ...
0
votes
0answers
28 views

Minimization of DFA

I have the following question I have minimized the DFA as the following since the states can only be partitioned to [S0][S1 S2] EDIT: Is my Minimization correct?
0
votes
0answers
15 views

Deterministic FSM accepting a binary string whose number of zero is either multiple of 2, 3, or both

I can build a FSM that accept binary string with multiple of 2 number of 0, and I can also build a FSM that accept binary string with multiple of 3 number of 0, but I cannot figure out how I can ...
0
votes
2answers
47 views

Using the Pumping Lemma to show that the language of all strings of even length having no $0s$ in their second half is not regular

I'm struggling with finding a starting string $s$ to prove using the Pumping Lemma that language $$L = \{w \mid w\text{ has even length and the second half of $w$ does not contain any $0$s}\}$$ is ...
0
votes
0answers
23 views

Finite automata dfa/nfa language problem review

I have completed the questions below but am not sure if they are correct. If anyone could help me confirm them it would be much appreciated. 3) This took me a little while but it seems to hold up. Im ...
0
votes
0answers
52 views

Panalphebetic strings provable by DFA?

Is the language of panalphabetic strings decidable by DFA? If so, how can I prove it? A string {a,…,z}* is said to be panalphabetic if it contains at least one occurrence of each letter.
0
votes
1answer
27 views

Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
0
votes
1answer
17 views

NFA Containing 'a'

I have L={Contains 'a'} and Alphabet(E)={a,b} Can i create a NFA Like this
0
votes
1answer
29 views

Wrong prove for $L=\{a^m:m\geq 0,\; m \mod 3\neq 0\}$ isn't regular, but why?

First, let me just say that this language is regular, and I understand why. But before I understood that, I tried proving that L isn't regular with pumping lemma. I just can't figure what is wrong ...
1
vote
1answer
20 views

Checking if $L_1 \cup L_2$ is regular language

Let $L_1=\{a^n b^r|n \geq 1, r\geq1,n=r\}$ $L_2=\{a^n b^r|n \geq 1, r\geq1,n\neq r\}$ be a non regular languages $L_1 \cup L_2$ is regular? I think that $L_1 \cup L_2$ is regular because we ...