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

learn more… | top users | synonyms

3
votes
1answer
27 views

Languages acceptable with just a single final state

For a given regular language $L$ we can always find a corresponding automaton with exactly one initial state, this is quite a common result and in most textbooks even non-deterministic automata are ...
1
vote
1answer
44 views

FSM to add two integer

Design a Mealy machine to add two integer(binary number). I can not determine how to deal with the carry.And what to do with the last carry generated.
1
vote
1answer
234 views

Converting the NFA produced from the language $a^nb^n : n\geq 0$ to a DFA to show its regular? Leading to question about pumping lemma.

I am reading about the pumping lemma, and having a hard time understanding it. I noticed that it is used to prove a language is not regular by contradiction. So you must first prove that a language in ...
0
votes
2answers
320 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
0answers
16 views

What is the pushdown automata for the language {0, 1}* Where |0| = 2 * |1| or |1| = 2 * |0|? [closed]

Having a lot of trouble figuring this out - I've been working at it for about four hours and have made zero meaningful progress. It seems to me to be impossible. I could do one side of the OR - but ...
0
votes
1answer
34 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
1
vote
0answers
2 views

Turing machine with k-dimensional tape or k-regular tree

The statement I read is " In a k-dimensional tape, cells corresponds to elements of free commutative group of k generators. s. There are 2k shifts, which correspond to addition of a generator ...
0
votes
1answer
1k 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$. But I ...
3
votes
1answer
48 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
0
votes
1answer
21 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
0
votes
0answers
8 views

Are transactions across petri net assumed to be running in parallel or there is always a predefined order?

I have a place $P$ with 3 marks in it and two outgoing immidiate Transitions [$t1, t2$] that require 1 token to fire. How marks flow are determined in Petri Net? Are there any Petri Net flavour ...
0
votes
1answer
410 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
0
votes
1answer
24 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
0answers
16 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
0answers
16 views

What is union of $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$

$L=L_1^+\cup L_2^*$ Where, $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$ My attempt: $L=L_1^+\cup L_2^*$ $L=(CSL)^+\cup (CSL)^*=CSL \cup CSL =...
0
votes
1answer
35 views

Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
0
votes
1answer
13 views

Find the classes of given languages?

Consider the following statements $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$ $L_2 = \{wy \mid w,y∈(a,b)^*\}$ $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$ $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$ Find the ...
0
votes
0answers
9 views

Prove that for any PDA there is another PDA that accepts exactly the same language bu has only one POP state.

Prove that for any PDA there is another PDA that accepts exactly the same language but has only one POP state. My attempt: Let the counter example $L=\{wcw^R|w\in(a,b)^*\}$ and string of $L$ is $...
0
votes
1answer
11 views

Possible strings of Kleene star of $L = \{a^nb^n|n≥1\}$

Consider the following CFL. $L = \{a^nb^n|n≥1\}$ Then which of the following string can be accepted by the kleene star of the language. $aaabbb$ $aabbaaabbab$ $abbaab$ $λ$ My attempt: The ...
0
votes
1answer
15 views

Is given statement decidable or undecidable?

A given non-terminal A in a given grammar CFG is ever used in the generation of word.-Decidable/undecidable? My attempt: It should be decidable problem, We can solve this problem using membership ...
0
votes
1answer
34 views

Design a Turing Machine which finds center of a given string with even length

A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model of computation that defines such a ...
0
votes
0answers
15 views

Non-Deterministic Push Down Automata popping when only the start symbol is in the stack.

I'm confused about NPDA, specifically about popping. if I had an automata that allows a lambda transition to a popping state that doesn't pop the start symbol what happens? Does it halt? To better ...
1
vote
1answer
12 views

An algorithm to decide if a context-free language like $L_1$ and a regular language like $L_2$ have common members

A context-free language (CFL) is a language generated by some context-free grammar (CFG). A regular language (also called a rational language) is a formal language that can be expressed using a ...
1
vote
1answer
23 views

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
0
votes
1answer
16 views

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$?

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$? My attempt : Using pumping lemma $L=\{a^mb^n|m\neq n \space, m,n\...
1
vote
0answers
16 views

If $G$ is $LL(k)$, then $L(G)$ is a deterministic context free language.

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). For every grammar, If the correct production can be deduced from the partially ...
1
vote
1answer
37 views

Although proven by pumping lemma language is not regular [closed]

We have to show, that although the language $L=\left\{qw^jq^k \mid j,k \in \mathbb N, j>k \mbox{ or }j \mbox{ is not even }\right\}$ satisfies pumping lemma, it is not regular. Okay, my try: For $...
1
vote
0answers
36 views

Turing Machine make use of another Turing Machine

I am expected to formally construct a deterministic TM to compute a function. I already have a TM for $f(x)$. How can I make use it formally while constructing $g(x)$? $g(x)$ is like in the followig ...
0
votes
3answers
31 views

DFA - Union operation: How to?

I'm currently looking at deterministic finite automata, and learning how to combine two DFAs using AND or OR. I think I understand how to construct the INTERSECTION (AND) of two DFAs, but I'm at a ...
2
votes
1answer
33 views

Countable State Automata

Consider an automaton with a countably infinite number of states. This machine could, given it's current state and a symbol from the input alphabet, move to another arbitrary state in a finite amount ...
-1
votes
1answer
23 views

CFG and Automata regular language and dFA questions

I have the following CFG questions which I am having a hard time getting my head around, I don't have any answers for them so I have no way of knowing if ive done them right or not (even though im ...
0
votes
1answer
28 views

proving not regular with pumping lemma

Not quite sure if I understand pumping lemma correctly. so if i have this language and i like to show it is not regular: L={ $q^a w^be^c| a,b,c \in N, a+b=c$}. If L would be regular, than there ...
0
votes
2answers
23 views

Constructing DFA - Criteria / Multiple solutions

I'm currently studying for my logic exam, and looking into examples on DFA construction. Assume the alphabet is {a, b}, and the language to be constructed is defined as follows: ...
0
votes
0answers
17 views

generating transition diagram and accepted language from prime number expression

I have the following expression and have to generate the diagram $(M(5))$ and accepted language $(M(5))$ for it, the issue is that I am having trouble even understanding what the expression is saying. ...
4
votes
2answers
42 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
0
votes
0answers
30 views

How to derive Turing Machine language?

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$: $$\begin{array}{c|cc} \delta&\vdash&a&b&c&\sqcup&\...
1
vote
0answers
17 views

How to make the NDPA of this question?

Say $w^R $ is the reverse of $w$. E.g.: $\epsilon^R = \epsilon$ and $(abbab)^R = babba$ Now say $L = \{ww^R | w \in L (a^*b^*)\}$ Draw the NDPA $M$ with $L(M) = M$ I understand NDPA's, however I ...
1
vote
2answers
29 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
0
votes
1answer
27 views

Prove that there exists an equivalent grammar in Chomsky Normal Form like $G'$ such that $G'$ has at most $(K-1)|P|+|T|$ production rules

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which ...
2
votes
1answer
34 views

Accurate model of a laptop when it is not connected to any external device

You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your ...
0
votes
2answers
648 views

Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?
2
votes
1answer
35 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
0
votes
0answers
19 views

How to decompose a Finite State Machine (FSM) into a cascade of two or more FSMs?

I am coming from Electrical Engineering background and would like to know how can I decompose a given FSM into a cascade of two or more FSMs. To be more precise, I am looking at following questions ...
0
votes
0answers
29 views

is this grammar ambiguous? and what is the recursive inference, the leftmost derivation and the parse tree for the word abcddd?

first question is, is this grammar ambiguous? how can i show that is there a way? and second question is what is the recursive inference, the leftmost derivation and the parse tree for the word ...
0
votes
1answer
33 views

Give a context-free grammar that generates the language

Give a context-free grammar that generates the language: $\{a^i b^j c^k d^h \mid i, j, h \geq 0, k>0 \text{ and } i+j \leq h\}$ This is what I've done so far: $S \rightarrow aSb \mid bSc \mid ...
5
votes
2answers
4k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
1
vote
0answers
33 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
0answers
20 views

What is an automata network?

I've tried Wikipedia and Google as first steps, but while I've found some interesting papers and articles, and a couple expensive textbooks, I've yet to find a clear definition of an automata network ...
0
votes
1answer
51 views

What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...